rahulsharmaah's blog

By rahulsharmaah, history, 5 weeks ago, In English

Your task is to build a tower whose width is 2 and height is n. You have an unlimited supply of blocks whose width and height are integers.

Input

=====

The first input line contains an integer t: the number of tests.

After this, there are t lines, and each line contains an integer n: the height of the tower.

Output

For each test, print the number of towers modulo 10^9+7.

Constraints

1≤t≤100 1≤n≤10^6

Example

Input:

3 2 6 1337

Output:

8 2864 640403945

Can anyone help me how can i solve this question any approach will be helpful **for full problem visit https://cses.fi/problemset/task/2413**

 
 
 
 
  • Vote: I like it
  • -11
  • Vote: I do not like it