ORDSUM23  Sums of 2 and 3
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:
20170322 09:48:59
Theory  https://en.wikipedia.org/wiki/Padovan_sequence 

vengatesh15:
20170307 09:35:38
easy one AC in 1 go:) 

sudeep_11:
20170127 21:01:17
my first dp ! AC in one go !


amit_taps1997:
20170106 18:03:02
Top Down TLE


mario_92:
20161118 20:51:32
Shouldn't this be in the Tutorial section?


nishkarshl:
20160729 07:54:01
The easiest DP ever. 

lalit_nit2:
20160712 13:17:00
Finally Done... Enjoyed my First DP :D Last edit: 20160712 13:32:57 

avisheksanvas:
20160708 06:26:55
Don't forget MOD 1000000007! 

chakkriii:
20160629 16:50:02
dp bottom up .


mehul712:
20160623 10:44:05
DP bottom up. Top down gives Segmentation Fault due to stack overflow. 
Added by:  Piyush Kumar 
Date:  20160614 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  Own Problem 