Yunzi được cho một ma trận hình chữ nhật kích thước ~n \times m~, ô ở vị trí ~(i, j)~ chứa số nguyên ~a_{i,j}~.

Ban đầu Yunzi đứng ở ô ~(1, 1)~ và muốn đi tới ô ~(n, m)~. Mỗi bước, Yunzi chỉ được đi sang phải hoặc đi xuống dưới: từ ô ~(i, j)~ cô có thể sang ô ~(i + 1, j)~ hoặc ô ~(i, j + 1)~.

Tuy nhiên, để đường đi trở nên thú vị hơn, Yunzi muốn tổng XOR của các số trong tất cả các ô mà cô đi qua (tính cả ô ~(1, 1)~ và ô ~(n, m)~) đúng bằng ~k~.

Hãy giúp Yunzi đếm số đường đi thú vị mà cô có thể đi.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên ~n~, ~m~ và ~k~.
• ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số nguyên; số thứ ~j~ của dòng thứ ~i~ là ~a_{i,j}~.

Kết quả

In ra một số nguyên duy nhất — số đường đi thú vị mà Yunzi có thể đi.

Ví dụ

Đầu vào:

3 3 9
2 3 4
3 4 4
2 3 8

Đầu ra:

3

Giải thích: Ba đường đi có tổng XOR bằng ~9~ đều đi qua các ô mang giá trị ~2, 3, 4, 4, 8~:

• ~(1,1) \to (1,2) \to (1,3) \to (2,3) \to (3,3)~
• ~(1,1) \to (1,2) \to (2,2) \to (2,3) \to (3,3)~
• ~(1,1) \to (2,1) \to (2,2) \to (2,3) \to (3,3)~

Ba đường đi còn lại có tổng XOR lần lượt là ~14~, ~14~ và ~8~.

Giới hạn

• ~1 \le n, m \le 20~
• ~0 \le k \le 10^{18}~
• ~0 \le a_{i,j} \le 10^{18}~

Số ô trên một đường đi là ~n + m - 1~, quá dài để duyệt hết ~2^{n+m-2}~ đường. Hãy cắt đường đi làm hai nửa tại đường chéo giữa và ghép hai nửa lại với nhau.