Alice và Bob chơi một trò chơi bằng cách luân phiên các lượt đi, Alice đi trước. Họ có một đồ thị có hướng không chu trình (DAG), sao cho mỗi cạnh $u \to v$ đều thỏa mãn $u < v$. Tất cả các đỉnh trong DAG này được tô một trong hai màu, và các đỉnh có chứa các quân cờ (một đỉnh có thể chứa nhiều hơn một quân cờ).

Trong lượt của mình, Alice sẽ chọn một đỉnh màu trắng $u$ có chứa ít nhất một quân cờ. Sau đó, cô ấy sẽ chọn một cạnh đi ra $u \to v$ và di chuyển một quân cờ từ đỉnh $u$ sang đỉnh $v$. Trong lượt của mình, Bob sẽ chọn một đỉnh màu đen $u$ có chứa ít nhất một quân cờ. Sau đó, anh ấy sẽ chọn một cạnh đi ra $u \to v$ và di chuyển một quân cờ từ đỉnh $u$ sang đỉnh $v$. Người không thể thực hiện nước đi sẽ thua cuộc.

Alice và Bob chưa quyết định cấu hình các quân cờ, nhưng họ đã quyết định rằng mỗi đỉnh khi bắt đầu trò chơi sẽ chứa tối đa một quân cờ. Trong số tất cả $2^n$ cách đặt quân cờ, hãy tính xem có bao nhiêu cách mà Alice sẽ thắng nếu cả hai người chơi đều chơi tối ưu? Vì giá trị này có thể rất lớn, hãy tìm kết quả theo modulo $998\,244\,353$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n, m$ ($1 \le n \le 300, 0 \le m \le \frac{n(n-1)}{2}$): số lượng đỉnh và số lượng cạnh trong đồ thị. Dòng thứ hai chứa một chuỗi có độ dài $n$. Nếu ký tự thứ $i$ là 'W', thì đỉnh đó là màu trắng. Ngược lại, nó sẽ là 'B' và là màu đen. Mỗi dòng trong số $m$ dòng tiếp theo chứa hai đỉnh $u, v$ ($1 \le u < v \le n$), biểu thị một cạnh $u \to v$. Đảm bảo rằng DAG sẽ không có đa cạnh.

Dữ liệu ra

In ra một số nguyên duy nhất: số lượng cách đặt tối đa một quân cờ trên mỗi đỉnh sao cho Alice thắng, theo modulo $998\,244\,353$.

Ví dụ

Ví dụ 1

5 4
WWWWW
1 2
2 3
3 4
4 5

30

Ví dụ 2

5 4
BWBWB
1 2
2 3
3 4
4 5

24

Ví dụ 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

300

Ví dụ 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

228

Ghi chú

Trong ví dụ đầu tiên, Alice sẽ thắng trong tất cả các trường hợp mà cô ấy có thể thực hiện ít nhất một nước đi (vì Bob sẽ không bao giờ có thể di chuyển), do đó kết quả là $2^5 - 2$.