Description

QCH 太 SB 了，什么数学题都不会，只好来问你。

以下是 QCH 的题目：

求

$$\sum_{k=1}^n\sum_{i=0}^k \sum_{j=i}^k \dbinom{i}{j} \mod 10^9+7 $$

的值。

Format

Input

第一行一个数 $T$ ,代表有 $T$ 个测试数据。
下面 $T$ 行一个数 $n$。

Output

一共 $T$ 行，每行为一个数代表答案。

Samples

1
8

1012

Limitation

$\sum$是指求和运算符，例如：

$$\sum^n_{i=1}a_i=a_1+a_2+......+a_n$$

$\dbinom{n}{m}$ 是指组合：

$$\dbinom{n}{m}=\dfrac{m!}{n!(m-n)!}$$

对于 $15* i\ (i\le4)\%$ 的数据，满足 $1\le n\le 10^i$，$1\le T\le 100$。
对于$100\%$的数据，满足 $1\le n\le 10^9$，$1\le T\le 1000$。