ストーリー

eiramくんはあおいさんが大好きなので、aoiの並びを見ると嬉しくなります。

問題文

各頂点に英小文字が書かれたある単純無向グラフ$H=(V_H, E_H)$に対して、このグラフのスコアを次のように定義します。

• $H$上の3頂点を通る単純パス$(v_1, e_1, v_2, e_2, v_3)$であって、次を満たすものの個数
  • 頂点$v_1, v_2, v_3$に書かれている文字はそれぞれa, o, iである

$N$頂点$M$辺の単純無向グラフ$G$があります。$i(1\leq i\leq M)$番目の辺は頂点$A_i$と頂点$B_i$の間に張られた辺です。
また、英小文字と?からなる長さ$N$の文字列$S$が与えられます。
$S$に含まれる?の個数を$q$としたとき、$S$に含まれる?を英小文字で置き換えてできる文字列$S'$として考えられるものは$26^q$個ありますが、そのすべてに対する次の値の総和を求めてください。

• $G$の各頂点$i(1\leq i\leq N)$に$S'_i$を書いてできるグラフのスコア($S'$の$i$文字目を$S'_i$で表す)

答えは非常に大きくなることがあるので$998244353$で割った余りを求めてください。

入力

$N\ M$
$S$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_M\ B_M$

• $3\leq N\leq 6000$
• $0\leq M\leq \min(6000, \frac{N(N-1)}{2})$
• $S$は英小文字および?からなる長さ$N$の文字列
• $1\leq A_i\lt B_i\leq N$
• $G$は単純無向グラフ. つまり$i\neq j\Leftrightarrow (A_i, B_i)\neq (A_j, B_j)$かつ$A_i\neq B_i$
• 入力は$S$を除いてすべて整数

出力

求める総和を$998244353$で割った余りを$r$として次の形式で1行に出力してください。

$r$

最後に改行してください。

サンプル

4 4
aoio
1 2
2 3
3 4
1 4

2

3 2
???
1 2
2 3

2

5 4
?ai?t
1 2
1 3
2 4
2 5

26