Đường đi XOR

Cho một lưới hình chữ nhật kích thước $n \times m $. Mỗi ô trong lưới chứa một số $ a_{i, j} $. Nhiệm vụ của bạn là tính số lượng đường đi từ ô góc trên bên trái \((1, 1)\) đến ô góc dưới bên phải \((n, m)\) thỏa mãn các điều kiện sau:

• Bạn chỉ có thể di chuyển sang phải hoặc xuống dưới. Cụ thể, từ ô \((i, j)\), bạn có thể di chuyển đến ô \((i, j+1)\) hoặc \((i+1, j)\).
• XOR của tất cả các số trên đường đi từ \((1, 1)\) đến \((n, m)\) phải bằng $ k $. (XOR là phép toán bitwise "hoặc loại trừ", ký hiệu là \(^\) trong C++ hoặc Java, và xor trong Pascal).

Hãy tính số lượng các đường đi thỏa mãn yêu cầu trong lưới đã cho.

Input

• Dòng đầu tiên chứa ba số nguyên $ n, m, k $ \((1 \leq n, m \leq 20, 0 \leq k \leq 10^{18})\): kích thước lưới và giá trị XOR cần đạt được.
• $ n $ dòng tiếp theo, mỗi dòng chứa $ m $ số nguyên, với số thứ $ j $ trên dòng thứ $ i $ là $ a_{i, j} $ \((0 \leq a_{i, j} \leq 10^{18})\).

Output

In ra một số nguyên duy nhất: số lượng đường đi từ \((1, 1)\) đến \((n, m)\) với tổng XOR bằng $ k $.

Example

3 3 11
2 1 5
7 10 0
12 6 4

3

3 4 2
1 3 3 3
0 3 3 2
3 0 1 1

5

3 4 1000000000000000000
1 3 3 3
0 3 3 2
3 0 1 1

0

Scoring

• \(30\%\) số test có \(n, m \leq 5\).
• \(30\%\) số test có \(n = 2\).
• \(40\%\) số test còn lại không có ràng buộc gì thêm.