Migrated from Lutece 3176 公园漫步

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

被老板压榨完之后的小u闷闷不乐，于是他决定来公园散散心

公园中央有一个$n×n$大小的方阵，第$i$行第$j$列格子填有数字$a_{i,j}$

小u对方阵上的数字来了兴趣，他提出了一个问题:

在方阵上行走时，遵循以下规则:

当前点为$(i,j)$，在不超出方阵范围的情况下，只能往$(i+1,j)$或者$(i,j+1)$走

遵守以上规则的情况下，从点$(1,1)$出发，到点$(n,n)$为止，有多少条路径的异或值为$0$？

路径的异或值为该路径上的所有数字进行异或操作得到的值

即$a_i \bigoplus a_{i+1} \bigoplus a_{i+2} \bigoplus \cdots \bigoplus a_j$

又菜又爱玩的小u同学想破脑袋也没想清楚怎么算，你能帮他算出答案吗？

Input

第一行输入一个数字$n$ 接下来的$n$行，每一行输入$n$个数字

Output

输出一行一个数字，即满足条件的路径个数

Samples

3
1 5 2
7 0 5
4 2 3

2

2
1 2
2 1

0

Constraints

$2\leq n \leq 20$, $0\leq a_{i,j}\leq 2^{30}$

Note

样例一满足条件的路径有2个，如下:

路径1:$(1,1)→(1,2)→(1,3)→(2,3)→(3,3)$

路径2:$(1,1)→(2,1)→(2,2)→(2,3)→(3,3)$

Resources

2024 UESTC ICPC Training for Search and Dynamic Programming