Đếm đường đi trên lưới

Cho một lưới gồm \(m\) hàng, \(n\) cột. Mỗi ô là ô trống (.) hoặc ô cấm (#). Một con robot đứng ở ô góc trên trái \((1, 1)\) và muốn đi tới ô góc dưới phải \((m, n)\). Mỗi bước robot chỉ được đi sang phải một ô hoặc xuống dưới một ô, và không được đi vào ô cấm.

Hãy đếm số đường đi khác nhau của robot, modulo \(10^9 + 7\).

Input

• Dòng đầu chứa hai số nguyên \(m\) và \(n\) (\(1 \le m, n \le 1000\)).
• \(m\) dòng tiếp theo, mỗi dòng là một xâu độ dài \(n\) gồm các ký tự . và #. Đảm bảo ô \((1, 1)\) và ô \((m, n)\) là ô trống.

Output

• In số đường đi, modulo \(10^9 + 7\).

Scoring

• Có \(30\%\) số test với \(m, n \le 10\).

Sample Input 1

3 4
....
.#..
....

Sample Output 1

4

Notes

Có 4 đường đi tránh ô cấm ở hàng 2, cột 2.