33741번 - actGenshinImp 다국어

문제

In the recent few years, this game has been so popular worldwide, it has even become a meme in the competitive programming community. Why would it be a bad idea to set problems about it?

You are given a grid $G$ of lowercase latin alphabets. A simple path on this grid is defined as a sequence of $k \ge 1$ distinct cells $p_1,p_2,\cdots,p_k,ドル such that $p_{i-1}$ and $p_i$ are adjacent either vertically or horizontally. Also, for some simple path $d$ of $m$ cells, let $f(d)$ be the string of length $m$ such that $(f(d))_i$ is the letter written on the cell $d_i$ of the grid $G$.

Please find the number of simple paths $a$ of 13ドル$ cells, such that $f(a)$ is a cyclic shift of "genshinimpact". As the answer may be very large, you are only required to find the value modulo 998ドル ,円 244 ,円 353$.

입력

The first line contains two integers $r$ and $c$ --- the number of rows and the number of columns of $G$. (1ドル \le r,c \le 500$)

Each of the $r$ following lines contains a string of length $c$ consisting of lowercase latin letters. The $i$-th of them is the $i$-th row of the grid $G$.

출력

Output the answer modulo 998ドル ,円 244 ,円 353$ on one line.

제한

노트

The grid in the sample input contains 8ドル$ simple paths satisfying the condition. The 8ドル$ simple paths are as follows.