# Shooting

**Background**

Abhinav is an indian shooter. In order to win the game he needs to make N points.He gets:

- 1 point for hitting the outer circle.
- 2 points for htiing the inner circle.
- 4 points for hitting the Bulls eye.

Being an inquisitive mind he wants to find out how many combinations of 1 point,2-point and 4 point hits can lead to a total score of N points.

**Input Specification**

- 1st line: An Integer T denoting the number of test cases.
- Each test Case Contains: An Integer N.

**Output Specification**

Output a single line containing the answer for this test case modulo 10000001.

**Sample Input**

` `

3

3623001

10

4

**Sample Output**

4791963

12

4

**Constraints**

- Number of Test Cases T , 1 < T <= 100
- 1<=N<=10^8

*Problem Setter : Vivek Bhatnagar*

*Time Limit : 0.5 Second*

**Languages:**C,C++,Java