Alice와 Bob

Alice와 Bob이 Alice부터 시작해 번갈아 턴을 두는 게임을 한다.

두 사람에게는 방향 비순환 그래프(DAG)가 주어지며, 모든 간선 $u \to v$는 $u < v$를 만족한다.

이 DAG의 모든 정점은 두 가지 색 중 하나로 칠해져 있고, 정점 위에는 토큰이 놓여 있다(한 정점에 토큰이 여러 개 있을 수 있다).

Alice는 자신의 턴에 토큰을 하나 이상 포함한 흰색 정점 $u$를 고른다. 그다음 나가는 간선 $u \to v$ 하나를 골라 정점 $u$에서 정점 $v$로 토큰 하나를 옮긴다.

Bob은 자신의 턴에 토큰을 하나 이상 포함한 검은색 정점 $u$를 고른다. 그다음 나가는 간선 $u \to v$ 하나를 골라 정점 $u$에서 정점 $v$로 토큰 하나를 옮긴다.

움직일 수 없는 사람이 진다.

Alice와 Bob은 아직 토큰 배치를 정하지 않았지만, 게임이 시작될 때 각 정점에는 토큰이 최대 하나만 놓이기로 했다. $2^n$가지 토큰 배치 중에서, 두 사람이 최적으로 플레이할 때 Alice가 이기는 배치의 수를 구하시오. 값이 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 구하시오.

첫째 줄에 두 정수 $n,m$이 주어진다($1 \leq n \leq 300, 0 \leq m \leq \frac{n(n-1)}{2}$). 이는 그래프의 정점 수와 간선 수이다.

둘째 줄에 길이 $n$의 문자열이 주어진다. $i$번째 문자가 W이면 정점 $i$는 흰색이다. 그렇지 않으면 B이며 검은색이다.

다음 $m$개의 줄에는 두 정점 $u$, $v$가 주어진다($1 \leq u < v \leq n$). 이는 간선 $u \to v$를 나타낸다.

DAG에 중복 간선은 없다.

각 정점에 토큰을 최대 하나만 놓는 배치 중 Alice가 이기는 배치의 수를 $998\,244\,353$으로 나눈 나머지를 출력한다.

첫 번째 예시에서 Alice는 한 번이라도 움직일 수 있는 모든 경우에 이긴다(Bob은 절대 움직일 수 없기 때문이다). 따라서 답은 $2^5 - 2$이다.