명령어 애너그램

로봇이 2차원 좌표평면의 원점, 즉 (0, 0)에 놓여 있다. 로봇은 {N, E, S, W}로 이루어진 N글자 문자열 S를 명령으로 받는다. 문자열의 처음부터 각 글자에 대해 로봇은 다음 방향으로 1만큼 이동해야 한다.

• 글자가 N이면 로봇은 y축 양의 방향으로 1만큼 이동한다.
• 글자가 E이면 로봇은 x축 양의 방향으로 1만큼 이동한다.
• 글자가 S이면 로봇은 y축 음의 방향으로 1만큼 이동한다.
• 글자가 W이면 로봇은 x축 음의 방향으로 1만큼 이동한다.

문자열 S는 알지 못한다. 대신 S의 애너그램인 문자열 P를 알고 있다. 즉 P는 S와 N, E, S, W의 개수가 각각 같다. 또한 M개의 데이터 (Ti, Xi, Yi)를 알고 있다. 모든 i에 대해 로봇이 정확히 Ti만큼 이동한 뒤 위치 (Xi, Yi)에 있다는 것을 안다.

주어진 정보를 모두 만족하는 가능한 문자열 S의 개수를 구하려고 한다.

첫 줄에 두 정수 N, M이 주어진다. (1 ≤ M ≤ N ≤ 400 000) N은 P의 글자 수, M은 데이터의 개수이다. 다음 줄에 {N, E, S, W}로 이루어진 N글자 문자열 P가 주어진다. 다음 M개 줄에 각각 세 정수 Ti, Xi, Yi가 주어진다. (1 ≤ Ti ≤ N; −Ti ≤ Xi, Yi ≤ Ti) 모든 i에 대해 Ti < Ti+1임이 보장된다.

주어진 정보를 모두 만족하는 가능한 문자열 S의 개수를 998 244 353으로 나눈 나머지를 한 줄에 출력한다. (잘못된 정보 등으로) 가능한 문자열 S가 없으면 0을 출력한다.