Alice y Bob juegan un juego por turnos alternos, comenzando Alice. Tienen un grafo acíclico dirigido (DAG), tal que cada arista $u \to v$ satisface $u < v$. Todos los vértices en este DAG están coloreados de uno de dos colores, y los vértices tienen fichas sobre ellos (un vértice puede contener más de una ficha).

Durante su turno, Alice elegirá un vértice blanco $u$ que contenga al menos una ficha. Luego, elegirá alguna arista saliente $u \to v$ y moverá una ficha del vértice $u$ al vértice $v$. Durante su turno, Bob elegirá un vértice negro $u$ que contenga al menos una ficha. Luego, elegirá alguna arista saliente $u \to v$ y moverá una ficha del vértice $u$ al vértice $v$. La persona que no pueda realizar un movimiento pierde.

Alice y Bob aún no han decidido la configuración de las fichas, pero han decidido que cada vértice al comienzo del juego contendrá como máximo una ficha. Entre todas las $2^n$ colocaciones de fichas, calcula cuántas de ellas ganará Alice bajo un juego óptimo de ambos jugadores. Como este valor puede ser grande, encuéntralo módulo $998\,244\,353$.

Entrada

La primera línea contiene dos enteros $n, m$ ($1 \le n \le 300, 0 \le m \le \frac{n(n-1)}{2}$): el número de vértices y aristas en el grafo. La segunda línea contiene una cadena de longitud $n$. Si el $i$-ésimo carácter es 'W', entonces el vértice es blanco. De lo contrario, será 'B' y será negro. Cada una de las siguientes $m$ líneas contiene dos vértices $u, v$ ($1 \le u < v \le n$), denotando una arista $u \to v$. Se garantiza que el DAG no tendrá aristas múltiples.

Salida

Imprime un entero: el número de formas de colocar como máximo una ficha en cada vértice de tal manera que Alice gane, módulo $998\,244\,353$.

Ejemplos

Entrada 1

5 4
WWWWW
1 2
2 3
3 4
4 5

Salida 1

30

Nota

En el primer ejemplo, Alice ganará en todos los casos donde pueda realizar al menos un movimiento (porque Bob nunca podrá moverse), por lo que la respuesta es $2^5 - 2$.

Entrada 2

5 4
BWBWB
1 2
2 3
3 4
4 5

Salida 2

24

Entrada 3

9 14
BWWBBBWWW
1 2
1 9
2 3
2 4
2 6
2 8
3 4
3 7
4 7
4 8
5 7
5 9
6 9
7 8

Salida 3

300

Entrada 4

10 15
BWBWBBWWBW
1 2
1 5
1 10
2 6
2 8
3 6
3 7
4 10
5 6
5 7
5 8
6 8
6 9
7 10
8 9

Salida 4

228