1454 - スロットマシン

時間制限 1 秒 / メモリ制限 256 MB / 得点 5 / Writer syoribu / x 1 / 統計 /


TLE
1sec
MLE
256MB
得点
5

問題文

アイヅ工業は新しいスロットマシンを開発しました。このスロットマシンは、$0$から$9$までの数字を横に $W$ 個、縦に $H$ 個表示します。 横方向の数字の並びを行、縦方向の数字の並びを列と呼びます。$W=5$、$H=3$ のときに表示される数字の例を図1に示します。


図1. スロットマシンに表示される数字の例$(W=5, H=3)$

このスロットマシンでは、表示された数字に応じて得点を得られます。得点は以下のように計算されます。 $1$列目から $w$ 列目すべてに特定の同じ数字が現れるとき(行の一致は問わない)、その数字を線で結んで$1$本の折れ線を作ることで得点(その数字)を得ることができます。 もし、形状が異なる複数の折れ線を作ることができる場合、すべての折れ線の得点の総和がスロットマシンで得られる得点になります。折れ線が一つも作れなければ、得点は$0$点になります。 図1に表示された数字で得られる得点を図2で考えます。


図2. スロットマシンの得点の計算例

図1の例では$3$がどの列にも現れるので、$3$を結んで折れ線が作れます。$5$列目に$3$が$2$つ現れるので、 図2に示すように$2$種類の折れ線が作れます。各折れ線の得点が$3$点なので、スロットマシンで得られる得点は$6$点になります。

課題

スロットマシンに表示されている数字が与えられたとき、得られる得点を求めるプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$W \ H$
$row_{1}$
$row_{2}$
$\vdots$
$row_{H}$

$1$行目に横方向の数字の個数$W \ (1 \leq W \leq 1,000)$と縦方向の数字の個数$H \ (1 \leq H \leq 1,000)$が与えられる。 続く$H$行に、$i$行目に表示される$W$個の数字の並び$row_{i}$が与えられる。$row_{i}$は$0$から$9$の数字からなる、長さ$W$の列である。

出力

得られる得点を $998,244,353$ で割った余りを$1$行に出力する。

入出力例

入力例1

5 3
03077
50333
35743

出力例1

6

入力例2

4 4
3351
5335
3573
7350

出力例2

28

入力例2では、$3$がどの列にも現れる折れ線が$6$本、$5$がどの列にも現れる折れ線が$2$本できる。よって、得点は $3 \times 6 + 5 \times 2 = 28$ となる。

入力例3

12 5
999999999999
999999999999
999999999999
999999999999
999999999999

出力例3

200776919