問題文

x の多項式 f(x) が文字列 S として与えられます。 ここで S は次の BNF 表記の <expr> シンボルで表されます。

<expr> ::= <term> | <expr> "+" <term> | <expr> "-" <term>
<term> ::= <factor> | <term> "*" <factor>
<factor> ::= <value> | <value> "^" <number>
<value> ::= <number> | "x" | "(" <expr> ")"
<number> ::= 1 以上 10^9 未満の整数　ただし先頭の 0 は省略される

記号はそれぞれ以下の意味を表します。

• x: x
• +: 足し算
• -: 引き算
• *: 掛け算、ただし足し算 + や引き算 - よりも先に計算される
• ^: 累乗、ただし足し算 + や引き算 - や掛け算 * よりも先に計算される

例えば、以下の文字列は上の <expr> シンボルになり得ます。

• x^2+3*x^1+5
  • f(x) = x^2 + 3\times x^1 + 5
• 1+2-3+4*5
  • f(x) = 1 + 2 - 3 + 4 \times 5
• ((x^123+1)^456)^789
  • f(x) = \left( \left(x^{123} + 1\right)^{456}\right)^{789}
• ((x))
  • f(x) = \left(\left(x\right)\right)
• 1^1*1
  • f(x) = 1^1 \times 1

また、以下の文字列は上の <expr> シンボルになり得ません。

• 2x
• 0^0
• 2^x
• -1
• 2^(1+2)
• 1000000000
• 007

f(x) の \bmod{10^K} での零点の数、すなわち f(n) \equiv 0 \pmod{10^K} を満たす 0 以上 10^K 未満の整数 n の個数を求めてください。

制約

• 入力は全て整数
• 1 \leq K \leq 9
• 1 \leq |S| \leq 100

入力例 1

2
x^2-x

出力例 1

4

• 入力される多項式は f(x) = x^2 - x を表しています。
• 以下の通り、n=0, 1, 25, 76 が条件を満たします。
  • f(0) = 0
  • f(1) = 0
  • f(25) = 600 \equiv 0 \pmod{100}
  • f(76) = 5700 \equiv 0 \pmod{100}

入力例 2

8
(((x))^234567890*1^1*1+(x^2)^2)

出力例 2

1000128

• 入力される多項式は f(x) = \left(\left(\left(x\right)\right)^{234567890} \times 1^1 \times 1+\left(x^2\right)^2\right) を表しています。

入力例 3

9
50+(2019-x+(x^3-x)^2019)*x^1

出力例 3

6

• 入力される多項式は f(x) = 50+\left(2019-x+\left(x^3-x\right)^{2019}\right) \times x^1 を表しています。