题号：NC20450
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
为了提高智商,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个数，表示攻击范围的模版。每个数字后面一个空格。
输出描述:
一个整数，表示可行方案Mod 2 ^32
备注:
对于10%的pn，
对于50%的pn，
对于100%的pn，