Đếm đường đi

Cho một lưới ô vuông gồm \(r\) hàng và \(c\) cột. Các hàng được đánh số từ \(1\) tới \(r\) theo thứ tự từ trên xuống dưới, các cột được đánh số từ \(1\) tới \(c\) theo thứ tự từ trái qua phải. Trên bảng có một số ô cấm.

Bạn cần đi từ góc trái trên \(–\) ô \((1, 1)\) tới góc phải dưới \(–\) ô \((r, c)\). Tại mỗi bước, bạn được đi theo một trong năm hướng như hình vẽ dưới đây:

\begincenter

\endcenter

Một đường đi được gọi là đường đi đẹp khi và chỉ khi đường đi có những tính chất sau:

• Mọi bước đi đều đi theo một trong năm hướng nêu trên.
• Hai bước đi liên tiếp nhau phải đi theo hai hướng khác nhau.
• Đường đi không đi qua ô cấm nào.

Ví dụ, đường đi dưới đây là một đường đi đẹp:

\begincenter

\endcenter

Đường đi dưới đây không phải đường đi đẹp vì có một bước đi không theo cả năm hướng trên:

\begincenter

\endcenter

Đường đi dưới đây không phải đường đi đẹp vì có hai bước đi liên tiếp theo cùng một hướng:

\begincenter

\endcenter

Đường đi dưới đây không phải đường đi đẹp vì có đi qua ô cấm:

\begincenter

\endcenter

Hãy đếm số đường đi đẹp từ ô \((1, 1)\) tới ô \((r, c)\).

Input

Dòng đầu tiên chứa hai số nguyên \(r\) và \(c\) \((1 \leq r, c \leq 2207)\) \(–\) số hàng và số cột của bảng.

\(r\) dòng tiếp theo, mỗi dòng chứa \(c\) kí tự mô tả bảng. Ký tự . thể hiện ô không cấm và ký tự # thể hiện ô cấm.

Dữ liệu vào đảm bảo hai ô \((1, 1)\) và \((r, c)\) đều không phải ô cấm.

Output

In ra một số nguyên duy nhất là số đường đi đẹp modulo \(998244353\).

Example

3 3
...
.#.
...

6

4 4
....
.##.
.#..
....

6

7 21
.....................
.####...#...#..#...#.
.#...#..#...#..#...#.
.####....#.#...#####.
.#.......#.#...#...#.
.#........#....#...#.
.....................

0

Scoring

• Subtask \(1\) (\(50\) điểm): \(r, c \leq 7\)

• Subtask \(2\) (\(50\) điểm): \(r, c \leq 2207\)