[TJOI2015] 棋盘

题目描述

为了提高智商,ZJY 去新世界旅游了。可是旅游过后的 ZJY 杯具地发现要打开通往原来世界的门,必须要解开门上面画的谜题。谜题是这样的: 有个 $n$ 行 $m$ 列的棋盘,棋盘上可以放许多特殊的棋子。每个棋子的攻击范围是 $3$ 行 $p$ 列。输入数据用一个 $3\times p$ 的矩阵给出了棋子攻击范围的模板,棋子被默认为模板中的第 $1$ 行,第 $k$ 列,则棋子能攻击到的位置是 $1$,不能攻击到的位置是 $0$。输入数据保证第 $1$ 行第 $k$ 列的位置是 $1$。打开门的密码就是,在要求棋子互相不能攻击到的前提下,摆放棋子的方案数。注意什么棋子都不摆放也算作一种可行方案。由于方案数可能很大,而密码为 $32$ 位的二进制密码,所以 ZJY 仅需要知道方案数对 $2^{32}$ 次方取余数的结果即可。 注意:编号从 $0$ 开始,即第 $1$ 行指的是中间那行。

输入输出格式

输入格式


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

输出格式


输出数据仅有一行,一个整数,表示可行的方案数模 $2^{32}$ 的余数。

输入输出样例

输入样例 #1

5 5
3 1
0 1 0
1 1 1
0 1 0

输出样例 #1

55447

说明

### 数据范围 对于 $10\%$ 的数据,$1 \leq n \leq 5$,$1 \leq m \leq5$。 对于 $50\%$ 的数据,$1 \leq n \leq 1000$,$1 \leq m \leq 6$。 对于 $100\%$ 的数据,$1 \leq n \leq 10^{6}$,$1 \leq m \leq 6$。