Limits 1s, 512 MB

At the beginning of time, there were only two circles in the circleverse (a universe where everyone is a circle). They are called the first generation of the circleverse and known as C(a)C(a) and C(b)C(b), where C(r)C(r) denotes a circle with radius rr.

Each year, a new generation of the circleverse is created from the previous one. Each generation of the circleverse consists of all circles in it positioned side by side on a straight line. To create the new generation, each pair of adjacent circles of the previous generation creates a new circle and positions it between them. The new circle gets a radius equal to the sum of the two adjacent circles it is created from. The figure below shows the first three generations of a circleverse.

Doctor Strange, the master of mystic arts, has explored the multiverse and found two circleverses C1C_1 and C2C_2. First generation of C1C_1 consists of circles C(0)C(0) and C(1)C(1). On the other hand, both circles of the first generation of C2C_2 are C(1)C(1). Doctor Strange wants to use C1C_1 and C2C_2 to create a new generation of circles he calls super-circles.

C(x)C(x) = iith circle of the nnth generation of C1C_1
C(y)C(y) = iith circle of the nnth generation of C2C_2
PP = number of circles in the nnth generation of a circleverse

Doctor Strange will create PP super-circles initially. The iith super-circle will be created from C(x)C(x) and C(y)C(y) and it will be C(x+y)C(x+y). After that, Doctor Strange will destroy all unstable super-circles. A super-circle C(x+y)C(x+y) is unstable if x>yx>y or y>ny>n. To destroy these unstable super-circles, he needs to summon enough energy from the multiverse. The amount of the energy required depends on the number of unstable super-circles.

Since Doctor Strange is the master of mystic arts, not mathematics, he needs your help to calculate the number of unstable super-circles. Given nn, calculate the number of the unstable super-circles Doctor Strange will have to destroy.


First line of the input will contain an integer TT, the number of test cases.
Each of the next TT lines will contain an integer nn, indicating that circles from the nnth generation will be used to create super-circles.



For each test case, print the number of the unstable super-circles modulo 109+710^9+7 in a single line.




Login to submit.


100% Solution Ratio
Reewnat.122Earliest, 1w ago
Reewnat.122Fastest, 0.5s
Reewnat.122Lightest, 236 MB
Reewnat.122Shortest, 863B
Toph uses cookies. By continuing you agree to our Cookie Policy.