All Submissions


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

Time Limit: 0.5 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0