Description

T 国有 $(n+1)×(n+1)$ 座城市，它们排成了一个方阵，每座城市与它周围城市联通，这里的周围包括八个方向（即正东，正西，正北，正南，东北，西北。东南，西南），其首都位于西南角。有一天 T 国国王 Tweetuzki 要从首都到达偏远的东南角的城市体察民情，沿途顺便观赏美景。由于不能耽误太多时间， Tweetuzki 每次必须向东行走。 Tweetuzki 想知道，从首都到达东南角城市有多少种不同的走法，由于数字可能过大，你需要对 $1\ 000\ 000\ 007$ 取模。

Input Format

输入文件名为city.in。

每个测试点中包含多组数据，对于每个测试点：

输入数据第一行一个正整数 $T$ ，表示数据组数。

接下来$T$行，每行一个正整数 $n$ ，表示 T 国大小。

Output Format

输出文件名为city.out。

对于每组数据，输出一行一个正整数，表示 Tweetuzki 有多少种不同的走法。

Sample

样例输入

1
3

样例输出

4

样例解释

我们设首都坐标为(0,0)，正东及正北为正方向，那么一共有$4$种走法：

1.(0,0)=>(1,0)=>(2,0)=>(3,0);
2.(0,0)=>(1,0)=>(2,1)=>(3,0);
3.(0,0)=>(1,1)=>(2,0)=>(3,0);
4.(0,0)=>(1,1)=>(2,1)=>(3,0);

Hint

对于$10\%$的数据，$n\le 20$。
对于$50\%$的数据，$n\le 1\ 000$。
对于$80\%$的数据，$n\le 10\ 000$。
对于$100\%$的数据，$n\le 1\ 000\ 000, T\le 10$。