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 containing the 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


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

hide comments
2017-01-27 21:01:17
my first dp ! AC in one go !
2017-01-06 18:03:02
Top Down TLE
Bottom Up AC
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
2016-07-29 07:54:01
The easiest DP ever.
2016-07-12 13:17:00
Finally Done... Enjoyed my First DP :D

Last edit: 2016-07-12 13:32:57
2016-07-08 06:26:55
Don't forget MOD 1000000007!
2016-06-29 16:50:02
dp bottom up .
good for begginers :)
2016-06-23 10:44:05
DP bottom up. Top down gives Segmentation Fault due to stack overflow.
2016-06-22 15:08:29 ALi Ibrahim
Couldn't be easier :\
2016-06-21 23:42:22 Amir Najjar
DP top down gives RE
Instead use DP Bottom Up.
And you get AC :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.