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
2020-09-05 09:16:12
Both top-down and bottom up works !!
2020-09-05 09:02:26
AC in 1 go!!
2020-04-04 16:01:52 Mauro Persano
If you think this problem is too easy, there's a really nice way to solve it (in log N) for really large N (e.g. 10^9).
2019-06-18 19:24:08
Top down works fine!
2019-06-09 14:36:55
Bottom up works...Top down doesn't.
2018-06-26 10:08:58
When spoj ques teach u smthing new : Padovan sequence :)
2018-03-02 13:50:02
how to see my own solution i cant retrieve please help
2018-02-16 14:43:40
Take care of mod,costed me 2 WA
2017-03-22 09:48:59
Theory - https://en.wikipedia.org/wiki/Padovan_sequence
2017-03-07 09:35:38
easy one AC in 1 go:-)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.