Slon's Expression

Slon is a student who never sits still in class. His teacher wants to keep him quiet, so she gives him a hard arithmetic problem.

The teacher writes an arithmetic expression $A$ and two integers $P$ and $M$. Slon has to answer this question: what is the smallest non-negative value of the variable $x$ for which the remainder of $A$ divided by $M$ equals $P$? An answer always exists.

Expanding $A$ with the distributive law never produces a term where $x$ is multiplied by $x$. In other words, $A$ is a polynomial of degree at most one in $x$.

The expression can evaluate to a negative number, so the remainder is always defined as the value between $0$ and $M - 1$.

Valid expressions look like 5+x*(3+2) and x+3*x+4*(5+3*(2+x-2*x)). Invalid expressions look like 5*(3+x*(3+x)) and x*(x+x*(1+x)).

The first line contains the expression $A$ ($1 \le |A| \le 100\,000$).

The second line contains two integers $P$ and $M$ ($0 \le P \le M - 1$, $1 \le M \le 1\,000\,000$).

$A$ consists only of the characters +, -, *, (, ), x and the digits 0 to 9. Brackets are always paired. Every +, - and * is applied to exactly two values, so an expression such as (-5) or (4+-5) never appears. Every multiplication is written out, so an expression such as 4(5) or 2(x) never appears either.

Print the smallest non-negative value of $x$ that satisfies the condition, on one line.

Take $A$ = 5+3+x, $P = 9$ and $M = 10$. For $x = 0$ the remainder is $8$, and for $x = 1$ the remainder is $9$, so the answer is $1$.