Nim game
Tag(s):

## Algorithms, Dynamic Programming, Dynamic Programming and Bit Masking, Medium

Problem
Editorial
Analytics

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

• First line: A single integer $T$ denoting the number of test cases
• For each test case:
• First line: A single integer $N$ denoting the number of heaps

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}$

SAMPLE INPUT
2
2
4
SAMPLE OUTPUT
0
1
Explanation

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

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

December Easy' 18

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Sorting