Lazy Links

Time limit: 1s Memory limit: 256MB Input: Output:

Task

Builder Bob is designing a new residential area in the city of Lazy Links. The area consists of nn houses, numbered from 1 to nn. The bidirectional streets between houses are built as follows:

  1. For each integer ii such that 1i<n1 \le i < n, there is a street between house ii and house i+1i+1.
  2. For each integer k1k \ge 1 such that 4kn4k \le n, there is a street between house 4k4k and house 4k34k - 3.

Bob envisions an ideal scenario where each player loots exactly two houses connected by a street. Each house can be looted by at most one player.

In how many different ways can the maximum number of players each loot two adjacent houses, such that no house is used more than once? Two ways are considered different if there is at least one pair of houses chosen in one arrangement and not in the other.

In other words, the question is: what is the number of maximum matchings that can be obtained?

Since the answer can be very large, output the result modulo 10000000071000000007.

Input data

The first line contains a single integer tt (1t10)(1 \le t \le 10) — the number of test cases.
Each of the next tt lines contains one integer nn (1n109)(1 \le n \le 10^9) — the number of houses in that test case.

Output data

For each test case, output a single integer — the number of distinct ways to select disjoint pairs of adjacent houses for the maximum number of players.

Example

stdin

3
8
3
127205

stdout

4
2
20761964

Explanation

For example, for nn=8, all four matchings are shown in the image below:

Log in or sign up to be able to send submissions!