测试数据来自 system/3026

作业已超过截止时间，您无法递交本题目。

排名

时间限制：200ms　内存限制：256M

---

【问题描述】

　　有\(n\) 名选手参加编程比赛，比赛完毕后主办方会对所有选手进行排名。比如有甲乙两人参加比赛，则最后的排名有三种可能性：
　　　● 1 1，即甲乙并列第一；
　　　● 1 2，即甲第一，乙第二；
　　　● 2 1，即甲第二，乙第一；
　　现在请你编程计算 \(n\) 名选手排名的可能性有多少种？

【输入格式】

　　第一行是一个整数 \(T\)，表示数据组数。接下来的 \(T\) 行，每行一个整数 \(n\)。

【输出格式】

　　每组数据输出一行，表示可能性的个数除以 20241223 的余数。

【输入输出样例】

　Input

4
1
3
4
100

　Output

1
13
75
12483183

【输入输出样例说明】

　　对于样例输入中的 \(n=3\)，有下列 13 种可能排名：
　　　　1 1 1
　　　　1 1 2
　　　　1 2 1
　　　　1 2 2
　　　　1 2 3
　　　　1 3 2
　　　　2 1 1
　　　　2 1 2
　　　　2 2 1
　　　　2 1 3
　　　　2 3 1
　　　　3 1 2
　　　　3 2 1

【数据说明】

　　对于 \(100\%\) 的数据 \(1≤T≤200000\)，\(1≤n≤1000\)。

【来源】

　　Mr.he