Đường Đi XOR Mục Tiêu

Cho một bảng hình chữ nhật gồm $n$ hàng và $m$ cột. Ô ở hàng $i$, cột $j$ chứa số nguyên không âm $a_{i,j}$.

Một đường đi bắt đầu tại ô $(1,1)$ và kết thúc tại ô $(n,m)$. Ở mỗi bước, bạn chỉ được đi sang ô ngay bên phải hoặc ô ngay bên dưới, miễn là ô đó vẫn nằm trong bảng. Giá trị của một đường đi là phép XOR theo bit của tất cả các số ghi trên những ô mà đường đi đi qua, bao gồm cả ô đầu và ô cuối.

Hãy đếm số đường đi có giá trị đúng bằng $K$.

Input

• Dòng đầu chứa ba số nguyên $n,m$ và $K$.
• Trong $n$ dòng tiếp theo, dòng thứ $i$ chứa $m$ số nguyên $a_{i,1},a_{i,2},\dots ,a_{i,m}$.

Output

• In một số nguyên: số đường đi từ $(1,1)$ đến $(n,m)$ có giá trị XOR bằng $K$.

Constraints

• $1\le n,m\le 20$.
• $0\le K\le 10^{18}$.
• $0\le a_{i,j}\le 10^{18}$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 10$ và $m\le 10$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

2 3 23
1 2 4
8 4 16

2