1979. [TJOI 2015] 棋盘

【题目描述】

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

【输入格式】

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

【输出格式】

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

【样例输入】

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

【样例输出】

7

【提示】

对于 $10\%$ 的数据，$1 ≤ n ≤ 5，1 ≤ m ≤ 5$;

对于 $50\%$ 的数据，$1 ≤ n ≤ 1000，1 ≤ m ≤ 6$;

对于 $100\%$ 的数据，$1 ≤ n ≤ 1000000，1 ≤ m ≤ 6$;