1290: #2104. 「TJOI2015」棋盘

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

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

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

输入格式

输入数据的第一行为两个整数 nnnmmm 表示棋盘大小。
第二行为两个整数 pppkkk,表示攻击范围模板的大小,以及棋子在模板中的位置。
接下来三行,每行 ppp 个数,表示攻击范围的模版。每个数字后面一个空格。

输出格式

一个整数,表示可行方案 mod232 的结果。

样例

样例输入

2 2
3 1
0 1 0
1 1 1
0 1 0

样例输出

7

数据范围与提示

1≤n≤106, 1≤m≤61 \leq n \leq 10^6, \ 1 \leq m \leq 61n106, 1m6