bee 2364 - Henrique

In the beginning of the computer, the professors require that the practical tasks of Algorithms and Data Structures II (AEDs II) should did in a language called DCCembly. Unfortunately, only one student was crazy enough to work with this language from scratch. This student was called Henrique. The other students did copies of his works, what sometimes ends with bugs.

In this problem, you should write a program that help detect those copies. Your program will receive as input two valid programs written in DCCembly and return as output how many inputs (modulo 10⁹ + 7) both programs give the same answer.

Return values: [I_i R v]
Stop the program and return a boolean value v ∈{0,1} as output.
Conditional Branch: [I_i D j I_k I_l]
Read the input x_j and branch the execution to the intruction of label I_k if x_j = 1 and I_l if x_j = 0.

We denote by var(I_i) the evaluate variable for an instruction. Therefore, if [I_i D j I_k I_l] is an instruction, var(I_i) = j. For instructions with return values like [I_i R v], we assume that var(I_i) = M + 1.

Every valid program in DCCembly should satisfy the following properties:

For each instruction with label I_i, exist an entry X = (x₁, …, x_M) such that I_i be ran when the program receive X.
For each branch instruction [I_i D j I_k I_l], we have var(I_i) < var(I_k) and var(I_i) < var(I_l).
An branch instruction only have target instructions that appeared previously in the code.
The execution begin in the last instruction.
The instruction labels are unique in a program.

Write a program the receive two valid source codes of DCCembly as input and return the number of different input which the both programs return the same value. Like the answer could be so large, compute that modulo 10⁹ + 7.

Input

The input is composed by many test cases. Each test case has one line with three integers: M, L₀ and L₁. The integer M (1 ≤ M ≤ 10⁶ ) mean the amount of variables in the input. L₀ mean the number of instructions in the first program (1 ≤ L₀ ≤ 1000) and L₁ mean the number of instructions in the second (1 ≤ L₁ ≤ 1000).

Following, there are L₀ lines having the first program source code. Branch instructions of type [I_i D j I_k I_l] are denoted by label I_i (1 ≤ I_i ≤ L₀) followed by the character “D” and three integers j, I_k, and I_l. The integer j indicates that variable x_j is evaluated by the branch (1 ≤ j ≤ M). Then, the integers I_k and I_l (1 ≤ I_k, I_l ≤ L₀) indicate the target instructions of the branch if x_j=1 and if x_j = 0, respectively. Finally, return instructions [I_i R v] are denoted by a numeric label I_i (1 ≤ I_i ≤ L₀) followed by the character “R” and an integer v ∈{0, 1}.

Finally, other L₁ lines describe the second program. As before, branch instructions of type [I_i D j I_k I_l] are denoted by label I_i (1 ≤ I_i ≤ L₀) followed by the character “D” and three integers j, I_k, and I_l. The integer j indicates that variable x_j is evaluated by the branch (1 ≤ j ≤ M). Then, the integers I_k and I_l (1 ≤ I_k, I_l ≤ L₀) indicate the target instructions of the branch if x_j=1 and if x_j = 0, respectively. Finally, return instructions [I_i R v] are denoted by a numeric label I_i (1 ≤ I_i ≤ L₀) followed by the character “R” and an integer v ∈{0, 1}.

Note that the labels are unique only inside the same program.

The input ends with a single line having three zeros, that shouldn't be processed.

Output

For each test case, output one single line having the number of different inputs (x₁, …, x_M) for that both programs return the same answer modulo 10⁹ + 7.

Input Sample	Output Sample
10 1 1 1 R 0 1 R 0 400 4 5 1 R 0 2 R 1 3 D 3 1 2 4 D 1 3 2 1 R 1 2 R 0 3 D 4 2 1 4 D 3 3 1 5 D 1 4 2 0 0 0	1024 824612832