问题描述

有 n 名选手参加编程比赛，比赛完毕后主办方会对所有选手进行排名。比如有甲乙两人参加比赛，则最后的排名有三种可能性：

　　　● 1 1，即甲乙并列第一；

　　　● 1 2，即甲第一，乙第二；

　　　● 2 1，即甲第二，乙第一； 　　现在请你编程计算 n 名选手排名的可能性有多少种？

输入格式

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

输出格式

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

样例输入

4
1
3
4
100

样例输出

1
13
75
12483183

数据范围

对于 100% 的数据 $1≤T≤200000，1≤n≤1000$。

思路：dp

/*  题解：
	设 dp[i] 表示有 i 个人时的排名方案数量
	首先可以发现方案是由 n 的全排列加上另外一个数求出来的
	所以可以先算出 n 的全排列数量 
	然后对于第一个人的排名，可以分为 n-1 类 
	第一类：第一个人的排名为 1，剩下的 n-1 个数有 dp[n-1] 种方法
	第二类：第一个人的排名为 2，剩下的 n-1 个数同样有 dp[n-1] 种方法
	...
	第 n-1 类：第一个人的排名为 n-1，剩下的 n-1 个数还是 dp[n-1] 种方法
	还有一种三个人都是第一名的情况，+1 即可 
	递推公式： dp[n]=dp[n-1]*(n-1)*2+1
	边界 ：dp[1]=0 
*/ 

求助！