题号:NC206243
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld
题目描述
保护野生动物,人人有责。
多多想从一块N × M大小的陆地中选取一块矩形陆地建立自然保护区,但是某些陆地已经有其他野生动物居住,多多选取时必须避开这些陆地,请问他有多少种选取方法呢?(正方形是特殊的矩形,答案可能过大,请对答案取模1000000007)
输入描述:
第一行输入两个正整数N,M (1 ≤ N ≤ 1000,1 ≤ M ≤ 1000)
接下来N行,每行输入长度为M的字符串。
(字符'O'代表可选陆地,字符'X'代表该陆地已有动物居住)
输出描述:
输出一个整数,为多多的选取方法(答案可能过大,请对答案取模1000000007)
示例1
说明
选取方法有5种,设左上角陆地为(1, 1)
第一种:选取(1, 2) 第二种:选取(2, 1)
第三种:选取(2, 2) 第四种:选取(1, 2),(2, 2)
第五种:选取(2, 1),(2, 2)
示例2
说明
可以看做有两个样例一的可选形状,所以选取方法有10种