有一个机器人位于坐标原点上。每秒钟机器人都可以向右移到一个单位距离，或者在原地不动。如果机器人的当前位置在原点右侧，它同样可以 向左移动单位距离。一系列的移动（左移，右移，原地不动）定义为一个路径。问有多少种不同的路径，使得$n$秒后机器人仍然位于坐标原点？ 答案可能很大，只需输出答案对$1,000,000,007$的模。
输入包含多组数据. 第一行有一个整数$T (1\leq T\leq 100)$, 表示测试数据的组数. 对于每组数据: 输入一个整数 $n (1\leq n\leq 1,000,000)$。
对于每组数据，输出一个整数
3 1 2 4
1 2 9