앨리스와 밥은 앨리스가 먼저 시작하는 번갈아 가며 진행하는 게임을 합니다. 그들은 각 간선 $u \to v$가 $u < v$를 만족하는 방향 비순환 그래프(DAG)를 가지고 있습니다. 이 DAG의 모든 정점은 두 가지 색상 중 하나로 칠해져 있으며, 정점 위에는 토큰이 놓여 있습니다(한 정점에 여러 개의 토큰이 있을 수 있습니다).

앨리스의 차례가 되면, 앨리스는 토큰이 하나 이상 있는 흰색 정점 $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 \to v$를 나타내는 두 정점 $u, v$ ($1 \le u < v \le n$)가 주어집니다. DAG에는 다중 간선이 없음이 보장됩니다.

출력

각 정점에 최대 하나의 토큰을 놓는 방법 중 앨리스가 승리하는 방법의 수를 $998\,244\,353$으로 나눈 나머지를 출력하십시오.

예제

입력 1

5 4
WWWWW
1 2
2 3
3 4
4 5

출력 1

30

입력 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

참고

첫 번째 예제에서, 앨리스는 적어도 한 번 움직일 수 있는 모든 경우에 승리합니다(밥은 절대 움직일 수 없기 때문입니다). 따라서 정답은 $2^5 - 2$입니다.