21011번 - Instruction Anagram 다국어

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: T_1...M, X_1...M, and Y_1...M. For all i, you know that the robot is at position (X_i, Y_i) after moving exactly T_i 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: T_i X_i Y_i (1 ≤ T_i ≤ N; −T_i ≤ X_i, Y_i ≤ T_i) representing the data points. It is guaranteed that T_i < T_i+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.