Alice i Bob grają w grę, wykonując ruchy na zmianę, przy czym Alice zaczyna jako pierwsza. Dysponują skierowanym grafem acyklicznym (DAG), w którym każda krawędź $u \to v$ spełnia warunek $u < v$. Wszystkie wierzchołki w tym grafie są pokolorowane na jeden z dwóch kolorów, a na wierzchołkach znajdują się żetony (wierzchołek może zawierać więcej niż jeden żeton).

W swoim ruchu Alice wybiera biały wierzchołek $u$, który zawiera co najmniej jeden żeton. Następnie wybiera pewną krawędź wychodzącą $u \to v$ i przesuwa jeden żeton z wierzchołka $u$ do wierzchołka $v$.

W swoim ruchu Bob wybiera czarny wierzchołek $u$, który zawiera co najmniej jeden żeton. Następnie wybiera pewną krawędź wychodzącą $u \to v$ i przesuwa jeden żeton z wierzchołka $u$ do wierzchołka $v$.

Osoba, która nie może wykonać ruchu, przegrywa.

Alice i Bob nie zdecydowali jeszcze o konfiguracji żetonów, ale ustalili, że na początku gry każdy wierzchołek będzie zawierał co najwyżej jeden żeton. Spośród wszystkich $2^n$ możliwych rozmieszczeń żetonów, oblicz, w ilu z nich Alice wygra przy optymalnej grze obu stron. Ponieważ wartość ta może być duża, podaj wynik modulo 998 244 353.

Input

Pierwsza linia zawiera dwie liczby całkowite $n, m$ ($1 \le n \le 300, 0 \le m \le \frac{n(n-1)}{2}$): liczbę wierzchołków i krawędzi w grafie.

Druga linia zawiera ciąg znaków o długości $n$. Jeśli $i$-ty znak to „W”, to wierzchołek jest biały. W przeciwnym razie będzie to „B” i wierzchołek jest czarny.

Każda z kolejnych $m$ linii zawiera dwa wierzchołki $u, v$ ($1 \le u < v \le n$), oznaczające krawędź $u \to v$.

Gwarantuje się, że graf DAG nie posiada wielokrotnych krawędzi.

Output

Wypisz jedną liczbę całkowitą: liczbę sposobów rozmieszczenia co najwyżej jednego żetonu na każdym wierzchołku tak, aby Alice wygrała, modulo 998 244 353.

Examples

Input 1

5 4
WWWWW
1 2
2 3
3 4
4 5

Output 1

30

Note

W pierwszym przykładzie Alice wygra we wszystkich przypadkach, w których może wykonać co najmniej jeden ruch (ponieważ Bob nigdy nie będzie mógł wykonać ruchu), więc odpowiedzią jest $2^5 - 2$.

Input 2

5 4
BWBWB
1 2
2 3
3 4
4 5

Output 2

24

Input 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

Output 3

300

Input 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

Output 4

228