During mathematics class, the students in the back row made a huge ruckus. Annoyed by the situation, the teacher did not let it slide and decided to assign a challenging task as punishment.
The task consists of a list, initially empty, of mathematical operations containing addition and multiplication. There are also $$$N$$$ instructions. Each instruction has one of the following formats:
- + $$$x$$$: Append an addition by $$$x$$$ to the end of the list of operations.
- * $$$y$$$: Append a multiplication by $$$y$$$ to the end of the list of operations.
- ? $$$z$$$: Starting from value $$$z$$$, apply the list of operations in order, and output the result modulo $$$10^{9} + 7$$$ – the remainder of the integer division by $$$10^{9} + 7$$$.
Given the list of instructions, help the students with the assigned task.
The input consists of several lines. The first line of the input contains the value of $$$N$$$ $$$(2 \leq N \leq 5 \times 10^{5})$$$.
Each of the next $$$N$$$ lines of the input contains an instruction as described in the statement – a character (+, * or ?) followed by a number $$$1 \leq x, y, z \leq 10^{9}$$$. It is guaranteed that the last instruction is of type '?' and that before the first instruction of type '?' there is at least one instruction of type '+' or '*'.
The output consists of several lines. Each line should contain an integer representing the answer for each instruction of type "? $$$z$$$". Print the answer modulo $$$10^{9} + 7$$$.
4+ 1* 3+ 2? 2
11
6* 1000000000+ 6? 1+ 1? 1? 998244353
1000000006 0 12289585
Explanation for example 1
The first query consists of the sequence of operations $$$2 \xrightarrow{+ 1} 3 \xrightarrow{\times 3} 9 \xrightarrow{+ 2} 11$$$.
