暂无测试数据。

Background

Description

T组数据，每次给定n，请求出下式的值，对10^9+7取模：
C(n, 0)* C(n, 0)+C(n, 1)* C(n, 1)+C(n, 2)* C(n, 2)+...+C(n, n)* C(n, n)

Format

Input

第一行一个整数T，表示数据组数。
接下来T行，每一行包含一个整数n，含义如题所示。

Output

输出T行，每行包含一个整数，表示对10^9+7取模后的答案。

Sample

Input

2
1
2

Output

2
6

Limitation

对于30％的数据，T<=500 , n<=10000。
对于100％的数据，T<=100000 , n<=1000000。
1s, 256000KiB for each test case.

Hint

Source

CDQZ TEST