LCC '22 Contest 6 S2 - Math Evaluation

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 128M

Problem type

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 ()0123456789x+.

Each number in the expression is less than 10^9 and will not contain leading zeros.

Input Specification

The first line contains a string S of N characters, the given expression.

Output Specification

The one and only line contains an integer, the final value of the expression modulo 10^9+7.

Sample Input


Sample Output


Sample Explanation

First evaluate the expression in the brackets first: 2\times 2=4.

Next, 3+4=7.

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.


There are no comments at the moment.