시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 0 0 0 0.000%

문제

A robot is placed at the origin of a 2D coordinate plane (i.e. position (0, 0)). The robot is given a string S containing N characters in {N, E, S, W} as its instructions. For each character from the beginning of the string, the robot has to move 1 unit to the following direction:

  • If the character is N, the robot has to move 1 unit to the positive y-axis direction.
  • If the character is E, the robot has to move 1 unit to the positive x-axis direction.
  • If the character is S, the robot has to move 1 unit to the negative y-axis direction.
  • If the character is W, the robot has to move 1 unit to the negative x-axis direction.

You do not know the string S. However, you know another string P that is an anagram of S (i.e. P has the same number of N, E, S, W characters as S). You also have M data points: T1...M, X1...M, and Y1...M. For all i, you know that the robot is at position (Xi, Yi) after moving exactly Ti units.

You want to know the number of possible string S that satisfies all the information you know.

입력

Input begins with a line containing two integers: N M (1 ≤ M ≤ N ≤ 400 000) representing the number of characters in P and the number of data points, respectively. The next line contains a string P containing N characters in the set {N, E, S, W}. The next M lines each contains three integers: Ti Xi Yi (1 ≤ Ti ≤ N; −Ti ≤ Xi, Yi ≤ Ti) representing the data points. It is guaranteed that Ti < Ti+1 for all i.

출력

Output in a line an integer representing the number of possible string S that satisfies all the information you know modulo 998 244 353. If there is no possible string S (possibly due to misinformation), output 0.

예제 입력 1

4 2
SNEN
2 1 1
4 1 1

예제 출력 1

4

The possible string S that satisfies all the information you know are {NENS, NESN, ENNS, ENSN}.

예제 입력 2

5 1
SSSSN
4 0 -4

예제 출력 2

1

The only possible string S that satisfies all the information you know is SSSSN.

예제 입력 3

7 1
NNNNSSS
4 1 -1

예제 출력 3

0

There is no possible string S that satisfies all the information you know.