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.
3 7gshimcteninpagppmpact
8
The grid in the sample input contains $$$8$$$ simple paths satisfying the condition. The $$$8$$$ simple paths are as follows.
