Evaluation of an Expression

You are given an expression $E$ built from integer constants $0$ through $9$, variables $a$ through $z$, and the operations of addition, multiplication, and exponentiation by a constant exponent. Remarkably, each of the variables $a, b, \dots, z$ appears in $E$ at most once.

For a given prime number $p$, we want to know how many roots the polynomial represented by this expression has modulo $p$. In other words, count the number of ways to assign integers from $0$ to $p-1$ to the variables in $E$ so that the value of $E$ is divisible by $p$. Since this number can be large, output it modulo $30011$.

For example, the expression $E = ((a+y) \cdot (z+8))^2$ has $15$ roots modulo $p = 3$, among which are:

$(a=0,\ y=0,\ z=0), \qquad (a=1,\ y=2,\ z=0), \qquad (a=2,\ y=0,\ z=1)$

Formally, an expression is defined as follows:

• Each integer constant $0, 1, \dots, 9$ is an expression.
• Each variable $a, b, \dots, z$ is an expression.
• If $A$ and $B$ are expressions, then both (A+B) and (A*B) are expressions: the former is the sum of $A$ and $B$, the latter is their product.
• If $A$ is an expression and $B$ is an integer constant from $2, 3, \dots, 9$, then (A^B) is an expression: it denotes $A$ raised to the power $B$.

The first line contains a prime number $p$ ($2 \le p < 15000$).

The second line contains an expression $E$ as defined above, given with no whitespace as a string of at most $300$ characters drawn from 0–9, a–z, +, *, ^, (, ).

Let $k$ be the number of roots of the polynomial $E$ modulo $p$. Output the single non-negative integer $k \bmod 30011$.