A student called Slon is very mischievous in school. He is always bored in class and he is always making a mess. The teacher wanted to calm him down and "tame" him, so he has given him a difficult mathematical problem.
The teacher gives Slon an arithmetic expression ~A~, the integer ~P~ and ~M~. Slon has to answer the following question: "What is the minimal non-negative value of variable ~x~ in expression ~A~ so that the remainder of dividing ~A~ with ~M~ is equal to ~P~?". The solution will always exist.
Additionally, it will hold that, if we apply the laws of distribution on expression ~A~, variable ~x~ will not multiply variable ~x~ (formally, the expression is a polynomial of the first degree in variable ~x~).
Examples of valid expressions ~A~: ~5 + x \cdot (3 + 2), x + 3 \cdot x + 4 \cdot (5 + 3 \cdot (2 + x - 2 \cdot x))~.
Examples of invalid expressions ~A~: ~5 \cdot (3 + x \cdot (3 + x)), x \cdot (x + x \cdot (1 + x))~.
The first line of input contains the expression ~A~ ~(1 \le |A| \le 100\,000)~.
The second line of input contains two integers ~P~ ~(0 \le P \le M - 1)~, ~M~ ~(1 \le M \le 1\,000\,000)~.
The arithmetic expression ~A~ will only consists of characters
x and digits from
The brackets will always be paired, the operators
* will always be applied to exactly two values (there will not be an expression
(4+-5)) and all multiplications will be explicit (there will not be an expression
The first and only line of output must contain the minimal non-negative value of variable ~x~.
Sample Input 1
5+3+x 9 10
Sample Output 1
Explanation for Sample Output 1
The remainder of dividing ~5 + 3 + x~ with ~10~ for ~x = 0~ is ~8~, and the remainder of division for ~x = 1~ is ~9~, which is the solution.
Sample Input 2
20+3+x 0 5
Sample Output 2
Sample Input 3
3*(x+(x+4)*5) 1 7
Sample Output 3