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 ~N~ 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 ~10^9+7~?
~1\le N\le 2\times 10^5~
~S~ contains only the characters
Each number in the expression is less than ~10^9~ and will not contain leading zeros.
The first line contains a string ~S~ of ~N~ characters, the given expression.
The one and only line contains an integer, the final value of the expression modulo ~10^9+7~.
First evaluate the expression in the brackets first: ~2\times 2=4~.
Hence, the expression is ~5\times 7+3\times 6=35+3\times 6=38\times 6=228~
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.