B. Bacterial Sampling
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a new bacteria that grows very fast. One of the local universities in town wants to breed some of this bacteria, their particular interest is to study the bacteria as an option to revert environmental damage because it is supposed to eat plastic! In order to calculate the required production, the university wants to know how much bacteria they can have in a container at minute $$$N$$$.

Several studies have shown the bacteria grows in the following way:

  1. A bacteria needs 2 minutes to mature.
  2. When a bacteria is mature, every 4 minutes it produces by meiosis 3 brand new bacteria.
  3. When a bacteria is 20 minutes old, it dies.

To start the experiment, the university at minute $$$0$$$ will put just 1 "new born" bacteria in the container. The university needs your help to know how much bacteria will be held in the container at minute $$$N$$$.

Input

The first line of input contains a number $$$T$$$ $$$(1 \leq T \leq 50)$$$ indicates the number of test cases. The next T lines contains a single integer $$$N$$$ $$$(1 \leq N \leq 10^9 )$$$, where the $$$i$$$-th line represents the minutes the university will let the experiment run on the $$$i$$$-th test case

Output

Print $$$T$$$ lines, where the $$$i$$$-th line contains a single integer, the amount of bacteria that will be on the container at minute $$$N$$$, since this number can be huge print it modulo $$$10^9 + 7$$$

Example
Input
4
1
2
3
12
Output
1
1
1
16