All submissions for this problem are available.
"...a composition of a positive integer n is a way of writing n as a sum of strictly positive integers. Two sums which differ in the order of their summands are deemed to be different compositions, while they would be considered to be the same partition."
- Quote from Wikipedia
How many compositions of a number n are with summands either 1 or 2.
The first line contains a number, the number of test cases (<= 1000000). Each subsequent line contains a number n (<= 1000000000).
Edit: The input actually contains n+1. That is, suppose the input is 10, you are required to output the answer for 9.
For test case print the solution mod 1000000007 on a new line.
Input: 3 2 4 6 Output: 1 3 8
|Time Limit:||1.30846 - 3.24 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.