Good Sequence

众所周知,
现有一个长度为 2*n 的序列,包含 n 个 1 和 n 个 -1 .
对于一个这样的序列,如果该序列的任意前缀和不小于 0 ,则称此序列为 "Good Sequence" ,
现给出 n ,求出长度为 2*n 的序列中有多少个 "Good Sequence" 。

输入包含多组数据。第一行为一个正整数 T ( 1 ≤ T ≤ 100 ),表示有 T 组测试数据。
对于每组测试数据,仅有一行包含一个整数 n ( 1 ≤ n ≤ 1000 )表示序列中分别含有 n 个 1 和 -1 .

对于每组测试数据，
输出一行包含一个整数,表示长度为 2*n 的序列中含有 "Good Sequence" 的个数，答案可能会很大，请将结果对 (313091025) 取模。

3
3
1
999

5
1
81644615

当n=3时,有5个"Good Sequence"分别为:(1,1,1,-1,-1,-1),(1,1,-1,1,-1,-1),(1,1,-1,-1,1,-1),(1,-1,1,1,-1,-1),(1,-1,1,-1,1,-1).当n=1时,有1个"Good Sequence",为(1,-1).

neromy