## 24 hour archive: Problem

###
** 2958
- Almost Complete Binary Tree** ** 2958 - Almost Complete Binary Tree** ** 2958 - Almost Complete Binary Tree**

#### Description

From Wikipedia: A

If the last level is NOT filled as far left as possible, we get an

Given integer

*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*.

**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

If the last level is NOT filled as far left as possible, we get an

Given integer

*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*.

**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

If the last level is NOT filled as far left as possible, we get an

Given integer

*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*.

**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).

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).

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).

#### 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

**T**(

**T**<= 100) to follow.

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

#### Sample input

`4`

4

10

21

73

#### Sample output

`3`

55

8007

473213758