A rectangular field of size
n*m is specified. Each cell contains a non-negative integer. You need to count the number of paths from cell (1,1) to cell (
n,
m) that satisfy the following conditions.
1) From each cell, you can only move
down or
right without leaving the field.
2) The bitwise exclusive
OR of all numbers on the path must be equal to
k.
Find the number of matching paths for the given field.
Input
The first line contains three integers
n,
m and
k (1 <= n, m <= 20, 0 <= k <= 10
18) - the height and width of the field, and the number
k.
The following
n lines each contain
m integers
ai,j, where
j -th element of
i-th row is equal to
ai,j (0 <= a
i,j < ;= 10
18).
Imprint
Print one integer - the number of paths that satisfy all conditions.
Examples
| # |
Input |
Output |
| 1 |
3 3 11
2 1 5
7 10 0
12 6 4
| 3 |
| 2 |
3 4 2
1 3 3 3
0 3 3 2
3 0 1 1
| 5 |