Right-Angled Snake Path Counting

Given an \(n \times m\) grid where some cells are blocked, count the number of right-angled snake paths satisfying the following conditions:

• The path starts at the center of some cell in the bottom row (row 1) and ends at the center of some cell in the top row (row \(n\)).
• From any cell, the snake may move one cell up, left, or right (i.e. it cannot move down).
• No cell may be visited more than once.
• The snake is not allowed to pass through blocked cells.

Output the total number of such paths modulo \(998244353\).

Note: The grid is provided as \(n\) lines of \(m\) characters each. The first input line after \(n\) and \(m\) corresponds to row 1 (the bottom row), and the \(n\)th line corresponds to row \(n\) (the top row). A character . denotes a free cell, and a character # denotes a blocked cell.

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space.

Then follow \(n\) lines, each containing a string of length \(m\) consisting of characters . and #, representing the grid. The first of these lines represents the bottom row of the grid, and the \(n\)th line represents the top row.

outputFormat

Output a single integer: the number of valid right-angled snake paths modulo \(998244353\).

sample

2 2
..
..

4