2958 - Almost Complete Binary Tree 2958 - Almost Complete Binary Tree 2958 - Almost Complete Binary Tree

Statistics Sub: 463 | AC: 286 | AC%: 61,77 | Score: 0,73
Created by Carlos Joa Fong
Added by cjoa (2014-06-15)
Limits
Total Time: 12000 MS | Test Time: 4000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

From Wikipedia: A Complete Binary Tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes [in the last level] are as far left as possible.


If the last level is NOT filled as far left as possible, we get an Almost Complete Binary Tree.



Given integer N, how many Almost Complete Binary Tree are there with exactly N nodes;jsessionid=9997613B243C123381AB82E70C8C4660? As the number may be too large, write out the answer mod 1000000007.
From Wikipedia: A Complete Binary Tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes [in the last level] are as far left as possible.


If the last level is NOT filled as far left as possible, we get an Almost Complete Binary Tree.



Given integer N, how many Almost Complete Binary Tree are there with exactly N nodes;jsessionid=9997613B243C123381AB82E70C8C4660? As the number may be too large, write out the answer mod 1000000007.
From Wikipedia: A Complete Binary Tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes [in the last level] are as far left as possible.


If the last level is NOT filled as far left as possible, we get an Almost Complete Binary Tree.



Given integer N, how many Almost Complete Binary Tree are there with exactly N nodes;jsessionid=9997613B243C123381AB82E70C8C4660? As the number may be too large, write out the answer mod 1000000007.

Input specification

First line of input contains the number of test cases T (T <= 100) to follow.

Each test case consists of a single line containing an integer N (1 <= N <= 3000).

;jsessionid=9997613B243C123381AB82E70C8C4660
First line of input contains the number of test cases T (T <= 100) to follow.

Each test case consists of a single line containing an integer N (1 <= N <= 3000).

;jsessionid=9997613B243C123381AB82E70C8C4660
First line of input contains the number of test cases T (T <= 100) to follow.

Each test case consists of a single line containing an integer N (1 <= N <= 3000).

;jsessionid=9997613B243C123381AB82E70C8C4660

Output specification

For each test case, output the answer (mod 1000000007) in a single line. ;jsessionid=9997613B243C123381AB82E70C8C4660
For each test case, output the answer (mod 1000000007) in a single line. ;jsessionid=9997613B243C123381AB82E70C8C4660
First line of input contains the number of test cases T (T <= 100) to follow.

Each test case consists of a single line containing an integer N (1 <= N <= 3000).

;jsessionid=9997613B243C123381AB82E70C8C4660

Sample input

4
4
10
21
73

Sample output

3
55
8007
473213758

Hint(s)




Recommendation

We have carefully selected several similar problems: 2156 | 2243 | 1873 | 2824 | 1946 | 3479