Though he rules all of WLMAC, Patrick is still subject to the burden of math homework. Hence, he has decided to recruit you, his trusty slave servant, to write him a program that'll do his math homework! His math homework can be expressed as one really giant equation, evaluated from left to right.
An equation a collection of characters, made up of brackets, digits representing numbers, x
characters representing a multiplication, and +
characters representing addition. When you evaluate an expression, you simply perform all of the operations from left to right. However, expressions surrounded by brackets will always be evaluated first. Now, given an expression, can you evaluate it and return the resulting number modulo ?
Constraints
contains only the characters ()0123456789x+
.
Each number in the expression is less than and will not contain leading zeros.
Input Specification
The first line contains a string of characters, the given expression.
Output Specification
The one and only line contains an integer, the final value of the expression modulo .
Sample Input
5x(3+(2x2))+3x6
Sample Output
228
Sample Explanation
First evaluate the expression in the brackets first: .
Next, .
Hence, the expression is
Notice that we evaluate from left to right - even though the B
part of BEDMAS is followed, multiplication is not necessarily performed before addition, rather the expression is evaluated left to right.
Comments