Consider $n$ piles of coins, with pile $i$ having $a_i$ coins. A valid move is to remove zero or more coins from each of the piles, with the constraint that atleast one pile should remain unchanged, and with the goal that after the move, the XOR sum of all the pile sizes should be $0$.
Given some game configuration (where the XOR sum or nim-sum is not already $0$), how many valid moves are possible, that bring the XOR sum to $0$?
The range of coins in each pile can range up to $10^9$ (30 bit numbers), and there could be around 100 piles, so a brute force is out of the question. The solution needs to be efficient in terms of time complexity.
This was a question I encountered in a programming contest, which is long since over and closed. I was trying to use induction to get a recursive formulation, but could not do so. How can we count the number of moves?