A. Цифры с двух сторон

Мише подарили число $n$. С ним разрешено делать три вещи:

• 1 X — приписать цифру $X$ в конец;
• 2 X — приписать цифру $X$ в начало;
• 3 — удалить цифру из начала.

После каждой операции выведите остаток числа от деления на $10^9 + 7$. Гарантируется, что после любой операции в числе остаётся хотя бы одна цифра.

В первой строке — число $n$ без ведущих нулей, в нём не больше $10^6$ цифр. Во второй строке — число операций $q$ ($1 \le q \le 10^5$). Далее $q$ строк с описаниями операций.

После каждой операции выведите остаток от деления текущего числа на $10^9 + 7$.