Problem E
Easy Arithmetic
Harry is now a third-year student at Hogwarts School of Witchcraft and Wizardry. Contrary to popular belief, arithmetic (known as Arithmancy in the wizard world) is crucial to becoming a powerful wizard.
For today’s Arithmancy homework, Harry is given a super long
expression
Harry must answer
-
: Compute the value of the expression from the -th character to the -th character, inclusive. As the value of this expression can be very large, Harry must calculate it modulo . -
: Change to the character .
Please help Harry!
Input
-
The first line contains
characters representing the expression . It is guaranteed that all characters are either digits or the + and - operators, and no two consecutive characters in are operators. -
The second line contains
. -
In the next
lines, each line contains one query:-
: representing a query of the first type. It is guaranteed that is a digit. -
, is either a digit or + or -: representing a query of the second type. It is guaranteed that after this query, no two consecutive characters are operators.
-
Output
For each query of the first type, print the value of the
expression, modulo
Sample Input 1 | Sample Output 1 |
---|---|
123-456+789 10 ? 2 5 ? 7 9 ? 4 6 ! 1 + ! 4 0 ? 1 7 ! 1 - ? 1 3 ? 4 7 ? 4 5 |
19 13 998244308 230456 998244330 456 4 |