盖房子
题号:NC52810
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 32 M,其他语言64 M
Special Judge, 64bit IO Format: %lld

题目描述

Bobo 在 ICPCCamp 买了一块 的土地,其中有些格子是障碍。
他想选择两个矩形区域,建造两座房子。
很明显,用于盖房子的区域不能包含障碍。同时,两个区域不能相交(但是可以相邻)。
Bobo 想知道所有可能不同方案的数量除以 的余数。

输入描述:

输入包含不超过 10 组数据。
每组数据的第一行包含两个整数 n, m ().
接下来 n 行中的第 i 行包含一个长度为 m 的字符串 s_is_i 的第 j 位是 `0` 则表示第 i 行第 j 列的格子是空地,是 `1` 则表示该格子是障碍。

输出描述:

对于每组数据,输出一个整数表示所求的值。
示例1

输入

复制
2 2
00
01

输出

复制
5
示例2

输入

复制
3 4
1000
0001
0100

输出

复制
160