Caminhos na Masmorra

#184

Made by: Crazynds

4000MB

Você está preso em uma masmorra representada por uma grade de $N$ linhas e $M$ colunas. Cada célula é ou livre (.) ou bloqueada (#).

Partindo da célula $(1,1)$ (canto superior esquerdo), você quer chegar à célula $(N,M)$ (canto inferior direito). A cada passo, você só pode se mover para a célula à direita ou abaixo da célula atual.

Conte o número de caminhos distintos de $(1,1)$ até $(N,M)$. Como esse número pode ser muito grande, imprima o resultado módulo $10^9 + 7$.

As células $(1,1)$ e $(N,M)$ são garantidamente livres.

Input

A primeira linha contém dois inteiros $N$ e $M$ $(1 \le N, M \le 10000,\ N \times M \le 10^7)$.

As próximas $N$ linhas contêm $M$ caracteres cada, sendo . (livre) ou # (bloqueada), sem espaços.

Output

Imprima um único inteiro: o número de caminhos módulo $10^9 + 7$.

Input Example

Output Example

3 3
...
.#.
...

3 3
...
...
...

3 3
.#.
#..
...

3 3
...
###
...

13 11
...........
#..#...#...
.#.........
.....#.....
...........
......##...
...........
....#......
...........
#....#....#
.........#.
...........
#..#.......