Алиса и Боб играют в игру, делая ходы по очереди, при этом Алиса ходит первой. У них есть ориентированный ациклический граф (DAG), в котором для каждого ребра $u \to v$ выполняется условие $u < v$. Все вершины в этом графе раскрашены в один из двух цветов, и на вершинах могут находиться фишки (в одной вершине может быть более одной фишки).

Во время своего хода Алиса выбирает белую вершину $u$, содержащую хотя бы одну фишку. Затем она выбирает некоторое исходящее ребро $u \to v$ и перемещает одну фишку из вершины $u$ в вершину $v$.

Во время своего хода Боб выбирает черную вершину $u$, содержащую хотя бы одну фишку. Затем он выбирает некоторое исходящее ребро $u \to v$ и перемещает одну фишку из вершины $u$ в вершину $v$.

Игрок, который не может сделать ход, проигрывает.

Алиса и Боб еще не определились с расстановкой фишек, но они решили, что в начале игры каждая вершина будет содержать не более одной фишки. Среди всех $2^n$ вариантов расстановки фишек вычислите, в скольких из них Алиса выиграет при оптимальной игре обоих игроков? Так как это число может быть большим, найдите его по модулю $998\,244\,353$.

Входные данные

Первая строка содержит два целых числа $n, m$ ($1 \le n \le 300, 0 \le m \le \frac{n(n-1)}{2}$): количество вершин и ребер в графе.

Вторая строка содержит строку длины $n$. Если $i$-й символ равен «W», то вершина белая. В противном случае он будет равен «B», и вершина будет черной.

Каждая из следующих $m$ строк содержит два целых числа $u, v$ ($1 \le u < v \le n$), обозначающих ребро $u \to v$.

Гарантируется, что в графе нет кратных ребер.

Выходные данные

Выведите одно целое число: количество способов расставить не более одной фишки на каждой вершине так, чтобы Алиса выиграла, по модулю $998\,244\,353$.

Примеры

Входные данные 1

5 4
WWWWW
1 2
2 3
3 4
4 5

Выходные данные 1

30

Примечание

В первом примере Алиса выигрывает во всех случаях, когда она может сделать хотя бы один ход (потому что Боб никогда не сможет сделать ход), поэтому ответ равен $2^5 - 2$.

Входные данные 2

5 4
BWBWB
1 2
2 3
3 4
4 5

Выходные данные 2

24

Входные данные 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

Выходные данные 3

300

Входные данные 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

Выходные данные 4

228