Description

作为小学生的小桂同学刚刚在老师的介绍下了解到了杨辉三角~(～￣▽￣)～。

好奇心旺盛的小桂同学产生了这样的问题：如果将杨辉三角中的数字全部向左端对齐，那么由第一行的第一个数字，第$n$行的最后一个数字以及第$2n−1$行的第一个数字为顶点所构成的等腰直角三角形内部的数字和是多少？

众所周知，小桂同学的数学很不好，于是他找到身为好朋友的你来帮忙解答这个问题。

$Note$：

$n$为$3$的杨辉三角如下图所示，红色三角形即为$n$为$3$时所构成的三角形。

杨辉三角（如下图所示）：
①杨辉三角的第一行为数字$1$。
②杨辉三角的每一行的第一个数字和最后一个数字都为$1$。
③杨辉三角第$n$行共有$n$个数字。
④除第一行与每行最左侧与最右侧的数字以外，每个数字等于它的左上方与右上方两个数字之和。

Input Format

第一行输入一个正整数$T$($1≤T≤10$)，表示共有$T$组测试样例。

对于每组测试样例：
输入一行，包含一个正整数$n$($1≤n≤10^6$)，表示直角顶点所在的行号。

Output Format

对于每组测试样例，输出一行，包含一个正整数，表示等腰直角三角形内部的数字和。

由于答案可能很大，请输出对$10^9$+7取模后的结果。

2
2 
3

4
12

Source

1816 Online Judge 10.100.0.232