L. Long integer
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given the positive integer $$$x_0$$$ in the decimal notation, and $$$q$$$ queries, the $$$i$$$-th of them can be one of two types:

  • Add some given digit $$$d_i$$$ to the right of the number, i.e. $$$x_i=\overline{x_{i-1}d_i}$$$.
  • Cross out the rightmost digit from the number, i.e. $$$x_{i-1}=\overline{x_ie_i}$$$.

After each query, print the remainder of dividing $$$x_i$$$ by $$$10^9+7$$$.

It is guaranteed that after each query the number will be positive ($$$x_i \ge 1$$$).

Input

The first line of the input file contains a single integer $$$x_0$$$.

The second line of the input file contains a single integer $$$q$$$.

The following $$$q$$$ lines denote the queries.

If the $$$i$$$-th query is a query to add a digit, then the $$$i$$$-th line contains the character "+" (without quotes) and $$$d_i$$$.

If the $$$i$$$-th query is a query to cross out a digit, then the $$$i$$$-th line contains the character "-".

$$$$$$ 1 \le x_0 \lt 10^{100\,000} $$$$$$ $$$$$$ 1 \le q \le 10^5 $$$$$$ $$$$$$ 0 \le d_i \le 9 $$$$$$

Output

After $$$i$$$-th query, print the remainder of dividing $$$x_i$$$ by $$$10^9+7$$$.

Examples
Input
123
3
+ 5
+ 1
-
Output
1235
12351
1235
Input
42
23
+ 0
+ 0
+ 0
+ 0
+ 0
+ 0
+ 2
+ 9
+ 4
+ 4
+ 2
-
-
-
-
-
-
-
-
-
-
-
-
Output
420
4200
42000
420000
4200000
42000000
420000002
200000001
0
4
42
4
0
200000001
420000002
42000000
4200000
420000
42000
4200
420
42
4