XOR-paths#8574
Given a rectangular field of dimensions n \times m, each cell contains an integer value. The value in cell is denoted as a_{i, j}. Your task is to determine the number of paths from the top-left corner cell to the bottom-right corner cell that meet the following criteria:
You can only move either down or to the right from any given cell. Specifically, from cell , you can move to cell (i, j + 1) or cell (i + 1, j), provided the move keeps you within the boundaries of the field.
The Xor of all the numbers along the path from cell to cell must be equal to .
Your goal is to calculate the number of such paths that satisfy these conditions.
The first line contains three integers , , and (1 \leq n, m \leq 20, 0 \leq k \leq 10^{18}), representing the height and width of the field, and the target number .
The following lines each contain integers, where the -th element of the -th row is a_{i,j} (0 \leq a_{i, j} \leq 10^{18}).
Output a single integer representing the number of paths from cell to cell where the xor of all numbers on the path equals .
Example 1
Example 2