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 ,test cases
T<=10000;
The next t lines ,each line contains N
N <=1e9
Output
The output should contain one line per testcase, 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}
hide comments
sanchit_aga:
20190108 12:35:35
Don't code a DP solution as it won't fit in the constraints. Try to come up with a general formula (you may need some knowledge of modular arithmetic at least for C++). 

shubham9466:
20160708 07:29:11
Last edit: 20160708 08:05:36 

muhammed yaseen:
20150725 22:17:18
Last edit: 20150725 22:20:29 

Manraj Singh:
20150606 10:37:50
I don't think we can solve it using Dynamic Programming since value of N is quite large. Correct me if I'm wrong. 

Ruffneck:
20150521 23:40:03
some large test cases please ? 

Sourav Saha:
20150430 16:06:45
@SanchitK : Answer for 5 : 56 

SanchitK:
20140328 22:28:13
what is the answer for n=5? 

Apoorv Jindal:
20131216 12:14:05
Pen and paper problem. :) Enjoyed solving it! Though the Dynamic Programming approach is pretty curious too. 

pranjuldb:
20130803 14:05:32
any hint....please :)


Amit Kumar Jha:
20130623 10:46:01
@Saurabh Kathpalia

Added by:  TouristGuide 
Date:  20130206 
Time limit:  1s2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Bytecode 2013 