题目描述
给定一个 n × m 的网格,每个格子为空格子或者障碍物,你可以不重叠地在空格子中放置若干个 1 × 2 的长方形拼图
对于每个空格子,你需要求出如果将这个格子改为障碍物,则有多少种放置拼图的方式,对 10^9 + 7 取模。
输入格式
第一行两个正整数 n,m,表示网格的行数和列数 接下来 n 行,每行 m 个数,Ai,1, Ai,2, · · · , Ai,m,其中 Ai,j = 0 表示第 i 行第 j 列为空格,Ai,j = 1 表示第 i 行第 j 列为障碍
输出格式
输出 n 行 m 列,第 i 行第 j 个数为 Bi,j,若网格中第 i 行第 j 列为空格,Bi,j 为该格变为障碍后的方案数,否则 Bi,j = 0
样例输入
2 4
0 0 0 0
0 0 0 1
样例输出
14 13 10 22
15 11 17 0
数据范围
对于前 10% 的数据,n ≤ 5, m ≤ 5
对于前 40% 的数据,n ≤ 12, m ≤ 12
对于另 10% 的数据,n ≤ 2, m ≤ 17
对于所有数据,n, m ≤ 17。