1290: #2104. 「TJOI2015」棋盘

为了提高智商，ZJY 去新世界旅游了。可是旅游过后的 ZJY 杯具地发现，要打开通往原来世界的门，必须要解开门上面画的谜题。

谜题是这样的：有一个 $n$ 行 $m$ 列的棋盘，棋盘上可以放很多特殊的棋子，每个棋子的攻击范围是 $3$ 行 $p$ 列。输入数据用一个 $3\times p$的矩阵给出了棋子攻击范围的模板，棋子被默认在模板中的第一行，第 $k$ 列，模板中棋子能攻击到的位置标记为 1，不能攻击到的位置是 0 $(1\le p\le m,0\le k<p)$。输入数据保证模板中的第一行第 $k$ 列是 1。

打开门的密码是这样的：在要求棋子互相不能攻击到的前提下，摆放棋子的方案数。注意什么棋子都不摆也算作一种可行方案。由于方案数可能很大，而密码为 $32$ 位的二进制密码，所以 ZJY 仅需要知道方案对 2322^{32}2​32​​ 取余的结果即可。