URI Online Judge | 2364

Henrique

By Filipe Arcanjo, UFMG BR Brazil

Timelimit: 1

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 109 + 7) both programs give the same answer.

Every valid program in DCCembly should satisfy the following properties:

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 109 + 7.

Input

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

Following, there are L0 lines having the first program source code. Branch instructions of type [Ii D j Ik Il] are denoted by label Ii (1 ≤ IiL0) followed by the character “D” and three integers j, Ik, and Il. The integer j indicates that variable xj is evaluated by the branch (1 ≤ jM). Then, the integers Ik and Il (1 ≤ Ik, IlL0) indicate the target instructions of the branch if xj=1 and if xj = 0, respectively. Finally, return instructions [Ii R v] are denoted by a numeric label Ii (1 ≤ IiL0) followed by the character “R” and an integer v ∈{0, 1}.

Finally, other L1 lines describe the second program. As before, branch instructions of type [Ii D j Ik Il] are denoted by label Ii (1 ≤ IiL0) followed by the character “D” and three integers j, Ik, and Il. The integer j indicates that variable xj is evaluated by the branch (1 ≤ jM). Then, the integers Ik and Il (1 ≤ Ik, IlL0) indicate the target instructions of the branch if xj=1 and if xj = 0, respectively. Finally, return instructions [Ii R v] are denoted by a numeric label Ii (1 ≤ IiL0) 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 (x1, …, xM) for that both programs return the same answer modulo 109 + 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