题号:NC15252
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld
题目描述
白兔有一个n*m的棋盘,某些格子是障碍。有k种大小为x*y的矩形图案(x<=2,且矩形不能旋转),每种数量无限个。
白兔可以在棋盘上任意放置图案,要求图案不能放到障碍上,且任意两个图案不相交。问方案数。
两种方案不同为存在一个格子在一种方案中被覆盖,在另一种方案中未被覆盖或者覆盖这两个格子的图案大小或位置不同。
一个矩形正好铺满x行y列的一块区域,不能旋转
输入描述:
第一行三个整数n,m,k(n,m<=15,k<=2*m)
接下来n行,每行m个整数,每个数为0或者1,1表示空格,0表示障碍
最后k行,每行两个数x,y(x<=2,y<=m),任意两对(x,y)不相同
输出描述:
一个数,表示答案,对1e9+7取模
示例1
输入
复制
2 3 2
1 0 0
1 1 0
1 1
1 2
示例2
输入
复制
4 4 2
1 0 0 1
0 0 0 0
1 1 1 1
0 1 1 0
1 1
1 2