식의 평가

정수 상수 $0$부터 $9$까지, 변수 $a$부터 $z$까지, 그리고 덧셈, 곱셈, 상수 지수를 사용한 거듭제곱 연산으로 이루어진 식 $E$가 있다. 놀랍게도 각 변수 $a, b, \dots, z$는 식 $E$ 안에 최대 한 번만 나타난다.

소수 $p$가 주어질 때, 이 식이 나타내는 다항식이 $p$를 법으로 하여 갖는 근의 개수를 구하려고 한다. 다시 말해, 식 $E$에 등장하는 각 변수에 $0$부터 $p-1$까지의 정수를 대입하는 방법 중에서 $E$의 값이 $p$로 나누어떨어지는 경우의 수를 센다. 이 개수가 매우 커질 수 있으므로, $30011$로 나눈 나머지를 출력하면 된다.

예를 들어 식 $E = ((a+y) \cdot (z+8))^2$은 $p = 3$일 때 근을 $15$개 가지며, 그중에는 다음과 같은 근들이 있다.

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

식은 다음과 같이 정의된다.

• 각 정수 상수 $0, 1, \dots, 9$는 식이다.
• 각 변수 $a, b, \dots, z$는 식이다.
• $A$와 $B$가 식이면 (A+B)와 (A*B)도 식이다. 앞은 $A$와 $B$의 합을, 뒤는 곱을 나타낸다.
• $A$가 식이고 $B$가 $2, 3, \dots, 9$ 중 하나의 정수 상수이면 (A^B)도 식이다. 이는 $A$를 $B$제곱한 것을 나타낸다.

첫째 줄에 소수 $p$가 주어진다. ($2 \le p < 15000$)

둘째 줄에 위에서 정의한 식 $E$가 주어진다. 식은 공백 없이 문자 0–9, a–z, +, *, ^, (, )로만 이루어지며, 길이는 최대 $300$자이다.

식 $E$가 나타내는 다항식이 $p$를 법으로 하여 갖는 근의 개수를 $k$라 하자. 음이 아닌 정수 $k \bmod 30011$을 하나 출력한다.