Alice et Bob jouent à un jeu en alternant les tours, Alice commençant en premier. Ils disposent d'un graphe orienté acyclique (DAG), tel que chaque arête $u \to v$ satisfait $u < v$. Tous les sommets de ce DAG sont colorés selon l'une des deux couleurs, et les sommets contiennent des jetons (un sommet peut contenir plus d'un jeton).

Lors de son tour, Alice choisit un sommet blanc $u$ qui contient au moins un jeton. Ensuite, elle choisit une arête sortante $u \to v$ et déplace un jeton du sommet $u$ vers le sommet $v$.

Lors de son tour, Bob choisit un sommet noir $u$ qui contient au moins un jeton. Ensuite, il choisit une arête sortante $u \to v$ et déplace un jeton du sommet $u$ vers le sommet $v$.

La personne qui ne peut pas jouer perd.

Alice et Bob n'ont pas encore décidé de la configuration des jetons, mais ils ont décidé que chaque sommet au début du jeu contiendra au plus un jeton. Parmi toutes les $2^n$ dispositions possibles des jetons, calculez combien d'entre elles permettent à Alice de gagner avec un jeu optimal des deux joueurs. Comme cette valeur peut être grande, donnez-la modulo $998\,244\,353$.

Entrée

La première ligne contient deux entiers $n, m$ ($1 \le n \le 300, 0 \le m \le \frac{n(n-1)}{2}$) : le nombre de sommets et d'arêtes dans le graphe.

La deuxième ligne contient une chaîne de caractères de longueur $n$. Si le $i$-ième caractère est 'W', alors le sommet est blanc. Sinon, il sera égal à 'B' et le sommet est noir.

Chacune des $m$ lignes suivantes contient deux sommets $u, v$ ($1 \le u < v \le n$), désignant une arête $u \to v$.

Il est garanti que le DAG ne contiendra pas d'arêtes multiples.

Sortie

Affichez un entier : le nombre de façons de placer au plus un jeton sur chaque sommet tel qu'Alice gagne, modulo $998\,244\,353$.

Exemples

Entrée 1

5 4
WWWWW
1 2
2 3
3 4
4 5

Sortie 1

30

Entrée 2

5 4
BWBWB
1 2
2 3
3 4
4 5

Sortie 2

24

Entrée 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

Sortie 3

300

Entrée 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

Sortie 4

228

Remarque

Dans le premier exemple, Alice gagnera dans tous les cas où elle peut effectuer au moins un mouvement (car Bob ne pourra jamais jouer), donc la réponse est $2^5 - 2$.