Server Time:

User's AC Ratio in this contest

100.0% (27/27)

Submission's AC Ratio in this contest

93.3% (28/30)

Description

小明最近找到一個超級稀有的玩具,世界上僅僅只有這麼一個。
小明非常想要得到這個玩具,但是因為它的稀有性,它的要價是個天文數字。

但是小明曾經從網路上學到「倍倍儲蓄法」這個神奇的方法。
這個方法非常簡單,就是每天都讓錢增加為前一天的兩倍。
用公式說明的話就是 $d_i = 2 \cdot d_{i - 1} \ \forall \ i > 1$,$d_i$ 代表第 $i$ 天小明有多少錢。

小明決定第一天先存 $1$ 塊錢($d_1 = 1$),並且為了規畫要存到什麼時候,小明希望你可以告訴他第 $N$ 天預計會有多少錢。

數字可能會非常大,因此輸出的時候請將實際數字與 $1000000007$ 做模運算之後再輸出。

Input Format

第一行有一個數字 $Q$,代表小明要問你幾次。
之後會有 $Q$ 行輸入,每行都只有包含一個整數 $N$,代表小明想要問第 $N$ 天的存款有多少。

  • $1 \leq Q \leq 100$
  • $1 \leq N \leq 2 \cdot 10^4$

Output Format

對於每次詢問請各輸出一個整數,代表 $d_N \mod 1000000007$。

Sample Input 1

3
1
2
3

Sample Output 1

1
2
4

Sample Input 2

1
1000

Sample Output 2

344211605

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~9 無特別限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1