URI Online Judge | 2364

# Henrique

By Filipe Arcanjo, UFMG 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.

• Return values: [Ii R v]

Stop the program and return a boolean value v ∈{0,1} as output.

• Conditional Branch: [Ii D j Ik Il]

Read the input xj and branch the execution to the intruction of label Ik if xj = 1 and Il if xj = 0.

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

Every valid program in DCCembly should satisfy the following properties:

• For each instruction with label Ii, exist an entry X = (x1, …, xM) such that Ii be ran when the program receive X.
• For each branch instruction [Ii D j Ik Il], we have var(Ii) < var(Ik) and var(Ii) < var(Il).
• 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 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