L. Long integer
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть целое положительное число $$$x_0$$$ в десятичной записи, а так же $$$q$$$ запросов, $$$i$$$-й из которых может быть одного из двух типов:

  • Приписать некоторую заданную цифру $$$d_i$$$ справа к числу, т.е. $$$x_i=\overline{x_{i-1}d_i}$$$.
  • Вычеркнуть крайнюю правую цифру из числа, т.е. $$$x_{i-1}=\overline{x_ie_i}$$$.

После каждого запроса выведите остаток от деления $$$x_i$$$ на $$$10^9+7$$$.

Гарантируется, что после каждого запроса число будет положительным ($$$x_i \ge 1$$$).

Входные данные

В первой строке входного файла содержится одно целое число $$$x_0$$$.

Во второй строке входного файла содержится одно целое число $$$q$$$.

Следующие $$$q$$$ строк содержат описание запросов.

Если $$$i$$$-й запрос это запрос на приписывание цифры, то $$$i$$$-я строка содержит символ «+» (без кавычек) и $$$d_i$$$ через пробел.

Если $$$i$$$-й запрос это запрос вычеркивания цифры, то $$$i$$$-я строка содержит символ «-».

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

Выходные данные

После $$$i$$$-го запроса выведите остаток от деления $$$x_i$$$ на $$$10^9+7$$$.

Примеры
Входные данные
123
3
+ 5
+ 1
-
Выходные данные
1235
12351
1235
Входные данные
42
23
+ 0
+ 0
+ 0
+ 0
+ 0
+ 0
+ 2
+ 9
+ 4
+ 4
+ 2
-
-
-
-
-
-
-
-
-
-
-
-
Выходные данные
420
4200
42000
420000
4200000
42000000
420000002
200000001
0
4
42
4
0
200000001
420000002
42000000
4200000
420000
42000
4200
420
42
4