SOLVE
LATER
Alice and Bob are playing the classic Nim game. In this version of the game, there are \(N\) heaps of stones. The \(i^{th}\) heap consists of \(i\) stones. In a single move, a player can select any non-empty heap and remove a positive number of stones from it. Alice starts the game, and both players move alternately. The player who cannot make a move in his or her turn loses the game.
Bob and Alice believe that the game is highly unfair to the second player. They both decide to give Bob an advantage. Before the game begins, Bob must select \(2\) distinct heaps \( i, j\) \((1\le i < j \le N)\) and combine them to form a single heap (the total number of heaps now will be \(N-1\) and the combined heap will contain \(i+j\) stones). The game, then begins as usual, with Alice making the first move. Both the players play optimally in the game.
Your task is to determine the number of ways in which Bob can select two distinct heaps such that after combining them, Bob has a winning strategy. Since the answer may be large, you have to calculate the answer modulo \(10^{9} + 7\).
Note: If in two ways, one of the selected heaps is different, then these two ways are considered different.
Input format
Output format
For each test case, print a single integer, on a new line, that represents the number of ways of winning for Bob modulo \(1000000007\).
Constraints
\(1 \le T \le 10\)
\(2 \le N \le 10^{18}\)
For the first test case, the initial state of the heaps is \([1, 2]\). There is only one way in which Bob can combine heaps. After his move, the state of the heaps becomes \([3]\). Alice then takes away all the stones from this heap in her move and wins the game.
For the second test case, the initial state is \([1, 2, 3, 4]\). Depending on Bob's move, the state of the heaps before Alice's move may be one of the following :
Combine \((1, 2)\) : \([3, 3, 4]\) - Alice wins
Combine \((1, 3)\) : \([2, 4, 4]\) - Alice wins
Combine \((1, 4)\) : \([2, 3, 5]\) - Alice wins
Combine \((2, 3)\) : \([1, 5, 4]\) - Bob wins
Combine \((2, 4)\) : \([1, 3, 6]\) - Alice wins
Combine \((3, 4)\) : \([1, 2, 7]\) - Alice wins