AT_ttpc2019_l 多項式の零点の個数

[problemUrl]: https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_l $ x $ の多項式 $ f(x) $ が文字列 $ S $ として与えられます。 ここで $ S $ は次の BNF 表記の `` シンボルで表されます。 > <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 $ - `+`: 足し算 - `-`: 引き算 - `*`: 掛け算、ただし足し算 `+` や引き算 `-` よりも先に計算される - `^`: 累乗、ただし足し算 `+` や引き算 `-` や掛け算 `*` よりも先に計算される 例えば、以下の文字列は上の `` シンボルになり得ます。 - `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 $ また、以下の文字列は上の `` シンボルになり得ません。 - `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 $ の個数を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ K $ $ S $

$ f(n)\ \equiv\ 0\ \pmod{10^K} $ を満たす $ 0 $ 以上 $ 10^K $ 未満の整数 $ n $ の個数を出力せよ。

### 制約 - 入力は全て整数 - $ 1\ \leq\ K\ \leq\ 9 $ - $ 1\ \leq\ |S|\ \leq\ 100 $ ### Sample Explanation 1 \- 入力される多項式は $ 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} $ ### Sample Explanation 2 \- 入力される多項式は $ f(x)\ =\ \left(\left(\left(x\right)\right)^{234567890}\ \times\ 1^1\ \times\ 1+\left(x^2\right)^2\right) $ を表しています。 ### Sample Explanation 3 \- 入力される多項式は $ f(x)\ =\ 50+\left(2019-x+\left(x^3-x\right)^{2019}\right)\ \times\ x^1 $ を表しています。