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
2016-06-20 17:07:39 Akshat Jain
I m solving in O(n), still it gives TLE...Any suggestions?

Re=> There's too much redundancy in your code.

Got it..Thanks..:)

Last edit: 2016-06-23 21:19:20
2016-06-20 12:37:08 ABHIJEET
top down is giving seg fault ..any suggestions .. :)
2016-06-20 03:47:14 mis94
I wonder why this code crashes when I try to enter 1000000
<code removed>

Re:Your code is crashing because the size of the array declared is less than the value of mod used to calculate the index of the array element that you are trying to access. Hence the variable's maximum value is more than size of the array, giving you Runtime Error.

Also, please don't post any code here. Use forum.

Last edit: 2016-06-20 06:32:49
2016-06-18 10:59:16
enjoyed it :D

Last edit: 2016-06-18 11:00:10
2016-06-18 10:59:14
First DP problem. :D

Last edit: 2016-06-18 10:59:32
2016-06-17 15:46:49 Sarthak Munshi
equal to coin change problem + order matters . one way to put it . easy if you observe the pattern .

Last edit: 2016-06-17 15:55:19
2016-06-16 14:49:00
This is a nice problem for people starting with Dynamic Programming :)
2016-06-16 12:41:14 Piyush Kumar
If the problem is too easy, should I consider moving it to tutorial?

=(Francky)=> An easy problem, for sure, but can stay here imho, unless it already exists in classical section with a similar form.

Re=> So, I am keeping it here for now. Thanks :)

Last edit: 2016-06-16 14:15:52
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.