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
shubham9466: 2016-07-08 07:29:11

Last edit: 2016-07-08 08:05:36
muhammed yaseen: 2015-07-25 22:17:18

Last edit: 2015-07-25 22:20:29
Manraj Singh: 2015-06-06 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: 2015-05-21 23:40:03

some large test cases please ?

Sourav Saha: 2015-04-30 16:06:45

@SanchitK : Answer for 5 : 56

SanchitK: 2014-03-28 22:28:13

what is the answer for n=5?

Apoorv Jindal: 2013-12-16 12:14:05

Pen and paper problem. :) Enjoyed solving it! Though the Dynamic Programming approach is pretty curious too.

pranjuldb: 2013-08-03 14:05:32

any hint....please :)
I am getting tle...is this subset sum problem....???

Last edit: 2013-08-03 14:06:10
Amit Kumar Jha: 2013-06-23 10:46:01

@Saurabh Kathpalia
0*0.25 0*0.5 0*1 1*2
0*0.25 0*0.5 2*1 0*2
0*0.25 2*0.5 1*1 0*2
0*0.25 4*0.5 0*1 0*2
2*0.25 1*0.5 1*1 0*2
2*0.25 3*0.5 0*1 0*2
4*0.25 0*0.5 1*1 0*2
4*0.25 2*0.5 0*1 0*2
6*0.25 1*0.5 0*1 0*2
8*0.25 0*0.5 0*1 0*2
10

Saurabh Kathpalia: 2013-06-15 05:47:55

@TouristGuide Can u explain the second test case I am getting 9
0*0.25 0*0.5 2*1
0*0.25 2*0.5 1*1
0*0.25 4*0.5 0*1
2*0.25 1*0.5 1*1
2*0.25 3*0.5 0*1
4*0.25 0*0.5 1*1
4*0.25 2*0.5 0*1
6*0.25 1*0.5 0*1
8*0.25 0*0.5 0*1
9
@Amit Thanks
Didn't read the problem statement carefully

Last edit: 2013-06-23 11:05:14

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