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.