CBANK - Charu and Coin Distribution
One day Charu went to deposit his pocket money in the Bank. But there was one problem that he wanted to deposit exactly "N" rupees, and he has coins of 0.25, 0.50, 1.0, and 2.0 rupees; and number of coins of each type are "4*N"; So he wants to know how many ways are there such that he can deposit exactly "N" rupees in bank using any number of coins of each type. As Charu is poor in counting he wants your help, Given input "N", give the number of ways of depositing "N" rupees using coins of 0.25, 0.50, 1.0, and 2.0 rupees. Since the answer can be really large, output the remainder when the answer is divided by 1000000007.
Input
First line will be t, number of test cases (T <= 10000). The next t lines, each line contains N (N <= 1e9).
Output
The output should contain one line per test case, representing the answer to the given problem.
Example
Input: 2 1 2 Output: 4 10
Explanation
In first case {.25, .25, .25, .25}, {.50, .25, .25}, {1}, {.50, .50}
Added by: | TouristGuide |
Date: | 2013-02-06 |
Time limit: | 1s-2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Bytecode 2013 |