XOR-paths
Given a rectangular field of dimensions n × m, each cell contains an integer value. The value in cell (i, j) is denoted as a[i, j]. Your task is to determine the number of paths from the top-left corner cell (1, 1) to the bottom-right corner cell (n, m) that meet the following criteria:
You can only move either down or to the right from any given cell. Specifically, from cell (i, j), 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 (1, 1) to cell (n, m) must be equal to k.
Your goal is to calculate the number of such paths that satisfy these conditions.
Input
The first line contains three integers n, m, and k (1 ≤ n, m ≤ 20, 0 ≤ k ≤ 10^18), representing the height and width of the field, and the target number k.
The following n lines each contain m integers, where the j-th element of the i-th row is a[i,j] (0 ≤ a[i, j] ≤ 10^18).
Output
Output a single integer representing the number of paths from cell (1, 1) to cell (n, m) where the xor of all numbers on the path equals k.