Animal Protection
题号: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

输入

复制
2 2
XO
OO

输出

复制
5

说明

选取方法有5种,设左上角陆地为(1, 1)
第一种:选取(1, 2)      第二种:选取(2, 1)
第三种:选取(2, 2)      第四种:选取(1, 2),(2, 2)
第五种:选取(2, 1),(2, 2)
示例2

输入

复制
3 3
XOO
OXO
OOX

输出

复制
10

说明

可以看做有两个样例一的可选形状,所以选取方法有10种
示例3

输入

复制
4 4
OOOX
OOXO
OOOO
XOOO

输出

复制
45