ORDSUM23 - Sums of 2 and 3

no tags 

Changu and Mangu are brothers. Changu likes 2 and Mangu likes 3. They decided to express each number as sum of 2 and 3.

They need your help. They want you to tell them the number of ways of writing a number as ordered sums of 2 and/or 3.

For example,  there are 4 ways to write 8 as an ordered sum of 2s and/or 3s:

 2 + 2 + 2 + 2

 2 + 3 + 3

3 + 2 + 3

3 + 3 + 2

Input

The first line contains T, the number of test cases. It is followed by T lines, each containg a number N.

Output

You have to print the number of ways of writing N as ordered sum of 2 and/or 3. You have to print the answer mod 1000000007.

Example

Input:

3

2

3

8

Output:

1

1

4

 

Constraints:

T<=100000

1<=N<=1000000



hide comments
julkas: 2017-03-22 09:48:59

Theory - https://en.wikipedia.org/wiki/Padovan_sequence

vengatesh15: 2017-03-07 09:35:38

easy one AC in 1 go:-)

sudeep_11: 2017-01-27 21:01:17

my first dp ! AC in one go !

amit_taps1997: 2017-01-06 18:03:02

Top Down TLE
Bottom Up AC

mario_92: 2016-11-18 20:51:32

Shouldn't this be in the Tutorial section?

Re: It should be but some users disagreed.

Last edit: 2016-12-01 05:39:13
nishkarshl: 2016-07-29 07:54:01

The easiest DP ever.

lalit_nit2: 2016-07-12 13:17:00

Finally Done... Enjoyed my First DP :D

Last edit: 2016-07-12 13:32:57
avisheksanvas: 2016-07-08 06:26:55

Don't forget MOD 1000000007!

chakkriii: 2016-06-29 16:50:02

dp bottom up .
good for begginers :)

mehul712: 2016-06-23 10:44:05

DP bottom up. Top down gives Segmentation Fault due to stack overflow.


Added by:Piyush Kumar
Date:2016-06-14
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own Problem