PYTHON

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 (3 + 2), x + 3 x + 4 (5 + 3 (2 + x 2 x)).

Examples of invalid expressions A: 5 (3 + x (3 + x)), x (x + x (1 + x)).

Input Format:

The first line of input contains the expression A

The second line of input contains two integers P and M.

The arithmetic expression A will only consists of characters +, -, *, (, ), x and digits from 0 to 9.

The brackets will always be paired, the operators +,-and * will always be applied to exactly two values (there will not be an expression (-5) or (4+-5)) and all multiplications will be explicit (there will not be an expression 4(5) or 2(x)).

Constraints:

1|A|100000

0PM-1

1M1000000

Time limit : 2 sec

Output Format:

The first and only line of output must contain the minimal non-negative value of variable x

Example input 1:

5+3+x 9 10

Example output 1:

1

Example input 2:

20+3+x 0 5

Example output 2:

2

Explanation:

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.

Please do this in python and make the code to take input as asked in the question.