Counting on Tree
All submissions for this problem are available.
In Fibonacci sequence,the first two numbers in the Fibonacci sequence are 0 and 1 and each subsequent number is the sum of the previous two.
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation:
F(n) = F(n-1) + F(n-2) where F(0)= 0, F(1)= 1.
For example, if one calls fibonacci(3), then the following will happen:
fibonacci(3) calls fibonacci(2) and fibonacci(1) (the first call).
fibonacci(2) calls fibonacci(1) (the second call) and fibonacci(0).
The second call of fibonacci(1) prints 1 and returns 1.
fibonacci(0) prints 0 and returns 0.
fibonacci(2) gets the results of fibonacci(1) and fibonacci(0) and returns 1.
The first call of fibonacci(1) prints 1 and returns 1.
fibonacci(3) gets the results of fibonacci(2) and fibonacci(1) and returns 2.
In total, '1' will be printed twice and '0' will be printed once.
Pooja is obsessed about counting number of 0's and 1's in any mathematical series.Once when she was constructing the recursion tree of fibonacci series,she thought to count the total number of 0's and 1's in the above tree.As she is new to data structures and algorithms she couldn't solve the problem.So she asked you to help her.Your task is to print how many times '0' and '1' respectively will be occured for a given N.
Since the answer can be very large,so you have to print answer modulo 10000007(10^7 +7).
The first line of the input contains an integer T denoting the number of test cases.The first line of each test case contains an integer N.
For each test case,you have to to print how many times '0' and '1' respectively will be occured for a given N.
Subtasks and Constraints
Subtask 1:(20 points)
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 16
Subtask 2:(80 points)
- 1 ≤ T ≤ 10^4
- 1 ≤ N ≤ 10^4
Input: 4 0 3 6 22 Output: 1 0 1 2 5 8 10946 17711
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, PYTH, PYTH 3.5, CS2|
Fetching successful submissions
If you are still having problems, see a sample solution here.