Nim game

3.4

5 votes
Algorithms, Dynamic Programming, Medium
Problem

Alice and Bob are playing the classic Nim game. In this version of the game, there are N heaps of stones. The ith 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 (1i<jN) and combine them to form a single heap (the total number of heaps now will be N1 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 109+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

1T10

2N1018

 

Sample Input
2
2
4
Sample Output
0
1
Time Limit: 1
Memory Limit: 256
Source Limit:
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

Editor Image

?