Note this problem was originally intended for the cancelled 2020 Girls Invitational Competition.

It's your first year of highschool! Unfortunately, you have already been targeted by bullies. On your way to class, you find yourself at the top left corner of an ~N~ by ~M~ hallway filled with ~K~ bullies! Every second, each of the bullies will step a certain number of units left, right, up or down. The bullies also have long legs, so it is possible that they may step right over you. As well, if they reach the edges of the hallway, they will pass right through them and disappear. Bullies are also friends with each other, so they can occupy the same square at a given point in time. If you are in their field of view, which is any units that they occupy or that are in front of them, they will throw one of their eggs at you!

The direction a bully is facing depends on its movement pattern. For example, if a bully moves ~5~ units left per second, they are facing left. The bully will only throw their eggs directly after they have finished taking a step, or in their initial position.

Your classroom is positioned at the bottom right of the hallway. Since you are fast, you will always move before the bully. Since you are also late, at any given point in time, you can only move one unit right or down. Can you output the number of ways to get to class without being hit by an egg, modulo ~10^9+7~?

Input Specification

The first line of input will contain three space-separated integers.

• ~N~ ~(1 \leq N \leq 10^3)~ is the length of the hallway.
• ~M~ ~(1 \leq M \leq 10^3)~ is the width of the hallway
• ~K~ ~(1 \leq K \leq 10^5)~ is the number of bullies.

The next ~K~ lines will contain ~3~ integers and one character separated by one space each, representing the state of one of the bullies.

• ~Y~ ~(1 \leq Y \leq N)~, the ~y~-position of one of the bullies.
• ~X~ ~(1 \leq X \leq M)~, the ~x~-position of one of the bullies.
• ~S~ ~(1 \leq S \leq 10^3)~, the distance one of the bullies moves in one second.
• ~D~, one of the four characters L, R, U, D, the direction one of the bullies moves in.

Output Specification

Output the number of ways to get to the bottom right corner of the hallway without being hit by an egg, modulo ~10^9+7~.

Subtasks

Subtask 1 [14%]

~N, M \leq 10~

~K = 1~

Subtask 2 [37%]

~N, M \leq 100~

~K \leq 10~

Subtask 3 [49%]

No additional constraints.

Sample Input 1

3 3 1
3 1 1 R

Sample Output 1

6

Explanation for Sample 1

Recreations for the hallway for the first three seconds are as follows:

By the time you reach the third row, the bully will be off the hallway. Thus, there are exactly 6 paths for you to move, shown below:

Sample Input 2

6 8 1
5 4 1 L

Sample Output 2

784

Note: You do not need to pass sample 3 for the first subtask.

Sample Input 3

5 6 2
3 1 1 U
4 5 2 D

Sample Output 3

0

Explanation For Sample 3

In the initial position, before either of you take a step, bully 1 is facing you, and can thus egg you. The positions that are in bully 1's field of vision in their initial position are marked in red in the following recreation of the hallway.