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.
- 1st line: An Integer T denoting the number of test cases.
- Each test Case Contains: An Integer N.
Output a single line containing the answer for this test case modulo 10000001.
- Number of Test Cases T , 1 < T <= 100
Problem Setter : Vivek Bhatnagar
Time Limit : 0.5 Second