Alchemical Transmutation Chain

A workshop has n alchemical stations arranged in a fixed line. Every batch of raw essence passes through station 1 first, then station 2, and so on through station n, in that exact order. Each station performs one of three transformations on the essence's magic value x as it passes through:

• ADD c — the value becomes x + c
• MUL c — the value becomes x * c
• SQR — the value becomes x * x

The workshop is given q separate starting values, one at a time; each one travels through the same chain of stations independently, starting fresh at station 1. Because repeated multiplication and squaring can make the magic value astronomically large, report every final value modulo 1,000,000,007.

Input format

• Line 1 contains a single integer n, the number of stations.
• Each of the next n lines describes one station, in order from station 1 to station n, in one of the forms ADD c, MUL c, or SQR (with no parameter).
• The next line contains a single integer q, the number of starting values.
• Each of the next q lines contains a single integer x, one starting magic value.

Output format

Print q lines. The i-th line contains the final magic value, modulo 1,000,000,007, obtained by sending the i-th starting value through the full chain of stations in order.

Constraints

• 1 ≤ n ≤ 1000
• 1 ≤ q ≤ 1000
• 0 ≤ c ≤ 10^9 for every ADD/MUL station
• 0 ≤ x ≤ 10^9 for every starting value

3
ADD 3
MUL 2
SQR
2
1
4

64
196

2
ADD 1000000000
SQR
1
1000000000

196