C. Um encontro no caminho

Time limit: 3000 msMemory limit: 256 MB

Um mapa tem $n$ linhas e $m$ colunas. Cada célula é livre (.) ou bloqueada (#). Uma rota vai de $(1,1)$ a $(n,m)$ , usa apenas células livres e, em cada passo, anda uma célula para baixo ou para a direita.

Conte os pares não ordenados de rotas distintas que têm exatamente uma célula em comum além da origem e do destino. Duas rotas são diferentes quando suas sequências de células são diferentes; trocar a ordem das duas rotas não cria outro par.

Imprima o resultado módulo $998\,244\,353$ .

Input

A primeira linha contém $n$ e $m$ ( $2\le n,m\le1500$ ).

Cada uma das próximas $n$ linhas contém $m$ caracteres ou , descrevendo uma linha do mapa. As células e são livres.

Output

Imprima a quantidade pedida, módulo $998\,244\,353$ .

Samples

Sample 1

Input

3 3
...
...
...

Output

Há dois pares cujo encontro adicional é $(2,2)$ e um par para cada uma das células $(1,2)$ , $(2,1)$ , $(2,3)$ e , totalizando seis.

C. Um encontro no caminho

Input

Output

Samples

Sample 1

Sample 2

Sample 3