D. 姬哥与考试周

众所周知，姬哥是个海王。还有 $2n$ 天就是考试周了。姬哥虽姬，犹有悔时。姬哥吸取了之前因为摸鱼期末考暴毙的教训，决定在期末考前金盆洗手，即和所有的金陵特产分手。但是姬哥发现自己恰有 $n$ 个金陵特产没有过深夜谈心，作为时间管理大师，姬哥非常不甘，想找你帮忙安排他的谈心计划。

在考试周前，姬哥每天可以和一个金陵特产进行深夜谈心，或者和一个金陵特产分手。当然，姬哥如果和某个金陵特产分手了，就无法再与她谈心。姬哥根据自己的喜好，心里已经对所有的金陵特产排好了序——即姬哥总会与排好序的金陵特产中第一个没有谈心 且没有分手的特产谈心，或与第一个没有分手的金陵特产分手。现在姬哥想要让你帮忙给出每天谈心或分手的方案，使得在考试周前他能与每个特产谈过心且分手。你能计算出一共有多少种可行方案吗？由于答案可能很大，请将答案对 $19260817$ 取模。

输入数据共 $t+1$ 行。

第一行一个正整数 $t(1 \leq t \leq 100000)$，表示有 $t$ 组测试数据。

接下来 $t$ 行，每行有一个正整数 $n(1 \leq n \leq 1000000)$，表示有 $n$ 个金陵特产，距离考试周 $2n$ 天。

对于每组测试数据，输出一行整数，表示方案数对 $19260817$ 取模。

样例输入

3
1
2
25

样例输出

1
2
15409410