Little Z has a magical vending machine containing $n \times m$ items, arranged in a grid with $n$ rows and $m$ columns. Every time Little Z inserts a coin into the vending machine, he receives a pair of items from adjacent cells (items already obtained can be obtained again). The probability of obtaining any specific pair of adjacent items is equal. Among these $n \times m$ items, some are liked by Little Z (items liked by Little Z are marked with * [asterisk], and others are marked with . [period]). He wants to package these items into a gift. Little Z wants to know the expected number of coins he needs to insert to obtain all the items he likes.

Input

The first line contains two integers $n$ and $m$.

The next $n$ lines each contain a string of length $m$, consisting only of the characters * and ..

Output

An integer representing the answer modulo $998244353$.

Examples

Input 1

1 3
***

Output 1

3

Input 2

3 3
..*
*.*
.*.

Output 2

404051295

Constraints

For all data, it is guaranteed that $1 \leq n \leq 6$ and $2 \leq m \leq 100$.

This problem uses bundled testing. Each subtask contains several test cases and is divided into 5 subtasks. You must pass all test cases in a subtask to receive the points for that subtask.

For convenience, let $cnt$ be the number of * in the input, and $s$ be the size of the largest connected component (4-connectivity) consisting of *.