Placing pawns.

A set of size $2n$ has $O_n$ subsets with an odd number of elements, and $E_n$ subsets with an even number of elements, where $O_n \; = \; \sum_{k=1}^{n} \binom{2n}{2k-1} \hspace{2cm} E_n \; = \; \sum_{k=0}^n \binom{2n}{2k}$ Note that $O_n + E_n \;= \; \sum_{k=0}^{2n}\binom{2n}{k} \; = \; 2^{2n} \hspace{2cm} E_n - O_n \; = \; \sum_{k=0}^{2n}(-1)^k\binom{2n}{k} \;= \; (1 - 1)^{2n} \; = \; 0$ and hence $O_n = E_n = 2^{2n-1}$ .

Thus there are $2^{2n-1}$ ways of putting pawns in one row of a $2n \times 2n$ chessboard so that there are an odd number of pawns in that row, and therefore there are $\big(2^{2n-1}\big)^{2n-1} = 2^{(2n-1)^2}$ ways of filling $2n-1$ of the rows of a $2n \times 2n$ chessboard so that each of these rows contains an odd number of pawns.

The parity (evenness/oddness) of the number of pawns so far in each of the $2n$ columns is fixed for any such choice, and therefore there is a unique decision to be made about the pawns that go in the last row which will ensure that all $2n$ columns have an odd number of elements in them. But then the chessboard will have an odd number of pawns in each of its $2n$ columns, and hence an even number of pawns on it altogether. The first $2n-1$ rows each have an odd number of pawns on them, and so the first $2n-1$ rows have an odd number of pawns on them altogether. Thus there must also be an odd number of pawns in the final row.

Thus the number of ways of filling a $2n \times 2n$ chessboard with pawns so that each row and each column contains an odd number of elements is $2^{(2n-1)^2}$ . For this question, $2^{19^2} \equiv 2^{361} \equiv \boxed{952} \pmod{1000}$ .

The key to this problem is realizing that, starting with a configuration satisfying the needed property, we can generate another one by picking a 2x2 square on the chessboard and reversing its state - namely, removing already existing pawns and placing pawns on the empty 1x1 squares within the 2x2 square's confines. This works, of course, because the parity of the number of pawns in each row and column remains unchanged. Note that for a 20x20 square, there's $19^2=361$ such 2x2 squares.

We conjecture that starting with any working configuration (for instance, one with pawns on one of the main diagonals only), we can generate all solutions simply by picking some subset of those $361$ squares and reversing their states. Furthermore, we conjecture that all generated solutions are distinct. If we prove these claims, then it is evident that there's a total of $2^{361}$ possible configurations, one for each subset of the 2x2 squares, making the answer $2^{361}\pmod{1000}$ . We have $2^{361}\pmod{8}=0$ and by Fermat's little theorem $2^{361}\pmod{125}=2^{61}\pmod{125}$ . Since $2^7=128=3\pmod{125}$ , $2^{63}=3^9=308\pmod{125}$ and $2^{61}=\frac{308}{4}=77\pmod{125}$ . Thus, from CRT, we have $2^{361}=952\pmod{1000}$ .

Now to prove the two claims:

First, let us prove that the generated solutions are distinct. Assume they are not, namely that there exist two different subsets of 2x2 squares which ultimately change the board in the same way. That means that after applying reversal of both subsets to the board, it remains unchanged. (It's worth mentioning that reversing a square twice, or indeed, an even number of times, is equivalent to not reversing it at all.) Since the subsets are different, there exists a square which was reversed exactly once. Because the board remained unchanged, the 1x1 squares it changed must've been "fixed" by reversing its surrounding 2x2 squares. However, that is impossible, because a surrounding square can either "fix" two of the "disturbed" 1x1 squares and "disturb" two others, ultimately keeping the number of "disturbed" 1x1 squares constant, or "fix" one but "disturb" three, making matters even worse. Therefore, it is impossible for the number of "disturbed" 1x1 squares to reach $0$ , hence the board cannot have remained unchanged. Thus, all generated solutions are distinct.

Now we need to confirm that there aren't any other solutions. Assume there are, namely that a solution exists which cannot be generated from the initial solution simply by reversing a subset of the $361$ 2x2 squares. Consider the 1x1 squares which differ between the two solutions - namely the ones which have a pawn in one but are empty in the other. Again due to the parity of the number of pawns, the number of these differing squares must be even in each row and column. We will now construct a subset of the 2x2 squares, after the reversal of which the board becomes empty. If we succeed, it is evident that we have a contradiction - by virtue of simply reversing 2x2 squares, we transformed one of the solutions into the other.

Consider the first row of the board. Each time we reach a differing 1x1 square, call it $s$ , we reverse the 2x2 square whose top left corner coincides with $s$ , hence emptying all the squares up to and including $s$ . Since the parity of the number of differing squares doesn't change either, by the time we reach the last square of the first row, the total number of first row 1x1 squares which differ must be $0$ . Doing the same procedure for the following rows, we can successfully empty all but the last row of the board. However, since all columns hold an even number of differing squares, the last row must be empty too, and we're done.