考虑一个表达式 $E$，其中包含 $0$ 到 $9$ 的整数常量，从 $a$ 到 $z$ 的变量，以及以下运算：加法、乘法和常数指数的幂运算。令人惊讶的是，每个变量 $a, b, \dots, z$ 在表达式 $E$ 中最多出现一次。对于给定的素数 $p$，我们想知道该表达式所表示的多项式在模 $p$ 意义下有多少个根。换句话说，我们想要计算有多少种方式可以将 $0$ 到 $p-1$ 之间的整数赋值给 $E$ 中的变量，使得 $E$ 的值能被 $p$ 整除。由于这样的根的数量可能很大，只需输出其模 $30011$ 的结果。

例如，由以下表达式表示的多项式： $$E = ((a + y) \cdot (z + 8))^2$$ 在模 $p = 3$ 下有 $15$ 个根，其中包括： $$(a = 0, y = 0, z = 0), \quad (a = 1, y = 2, z = 0), \quad (a = 2, y = 0, z = 1)$$ 等。

更正式地，表达式定义如下： 每个整数常量 $0, 1, \dots, 9$ 都是一个表达式。 每个变量 $a, b, \dots, z$ 都是一个表达式。 如果 $A$ 和 $B$ 是任意表达式，则 $(A+B)$ 和 $(AB)$ 也是表达式：前者是表达式 $A$ 和 $B$ 的和，后者是它们的积。 * 如果 $A$ 是任意表达式，且 $B$ 是 $2, 3, \dots, 9$ 中的整数常量，则 $(A^B)$ 也是表达式：即表达式 $A$ 的 $B$ 次幂。

输入格式

第一行包含一个素数 $p$ ($2 \le p < 15000$)。第二行包含如上所述的表达式 $E$，由最多 $300$ 个字符 $0, 1, \dots, 9, a, b, \dots, z, +, *, \text{\textasciicircum}, (, )$ 组成的序列表示，中间没有空格。

输出格式

令 $k$ 表示多项式 $E$ 在模 $p$ 意义下的根的数量。你的程序应输出一个非负整数，$k \pmod{30011}$。

样例

输入 1

3
(((a+y)*(z+8))^2)

输出 1

15