展台被分成N*N个格子，某些格子中有钻石，为了防盗，需要建立防盗系统，防盗系统是一种光电检测装置，它可以检测它所在的行和列以及两个对角线共四条线上是否有人触碰。当然已经放置了钻石的位置是不能安装这个装置的，同时四条线上不能有多个装置，因为他们会互相干扰，发出错误的信号。针对以上防盗装置，放置N个检测装置，我们想知道有多少种布局方案。

第一行一个整数N，表示展台的大小。

接下来 N 行，每行N个0或1的整数，如果一个整数为1，表示对应的位置可以放防盗装置，如果一个整数为0，表示对应的位置放置了展品。

一个整数，表示总共有多少种放法。

4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1

1