Story

eiram loves Aoi, so he gets happy whenever he sees the sequence aoi.

Problem Statement

For a simple undirected graph $H=(V_H, E_H)$ with a lowercase English letter written on each vertex, the score of this graph is defined as follows.

• The number of simple paths $(v_1, e_1, v_2, e_2, v_3)$ through 3 vertices on $H$ that satisfy the following:
  • The letters written on vertices $v_1, v_2, v_3$ are a, o, i, respectively.

There is a simple undirected graph $G$ with $N$ vertices and $M$ edges. The $i(1\leq i\leq M)$-th edge connects vertex $A_i$ and vertex $B_i$.
You are also given a string $S$ of length $N$ consisting of lowercase English letters and ?.
Let $q$ be the number of ? in $S$. There are $26^q$ possible strings $S'$ obtained by replacing each ? in $S$ with a lowercase English letter. Over all of them, find the sum of the following value.

• The score of the graph obtained by writing $S'_i$ on each vertex $i(1\leq i\leq N)$ of $G$ (where $S'_i$ denotes the $i$-th character of $S'$)

Since the answer can be very large, find it modulo $998244353$.

Input

$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$ is a string of length $N$ consisting of lowercase English letters and ?
• $1\leq A_i\lt B_i\leq N$
• $G$ is a simple undirected graph. That is, $i\neq j\Leftrightarrow (A_i, B_i)\neq (A_j, B_j)$ and $A_i\neq B_i$
• All values in the input except $S$ are integers

Output

Let $r$ be the desired sum modulo $998244353$. Output it on one line in the following format.

$r$

Print a newline at the end.

Sample

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