Getting to X

All submissions for this problem are available.
Alice is playing a game. In this game, she either gets 2 or 3 points in each move. What is the number of ways in which she can get a score of X?
Since X can be quite large, report the answer modulo 1000000009.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case is described by a single line containing 1 integer X denoting the score Alice wants to get.
Output
For each test case, output a single line containing a single integer denoting the number of ways to get score X, modulo 1000000009.
Constraints
Subtask 1:
 1 ≤ T ≤ 25
 1 ≤ X ≤ 10^{7}
Subtask 2:
 1 ≤ T ≤ 25
 1 ≤ X ≤ 10^{17}
Example
Input: 5 1 2 3 4 5 Output: 0 1 1 1 2
Explanation
Example case 1. Getting a score of 1 is not possible.
Example case 2. You can get a score of 2 in only 1 way.
Example case 3. You can get a score of 3 in only 1 way.
Example case 4. You can get a score of 4 in only 1 way  2, 2.
Example case 5. You can get a score of 5 in 2 ways  2, 3 or 3, 2.
Author:  inoi_admin 
Tags  inoi_admin 
Date Added:  8112014 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 