AT_ttpc2019_l 多項式の零点の個数

现给定一个表示多项式 $ 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$ 的整数（不含前导零） 其中，各符号表示如下： - `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` 请计算：在 $\bmod{10^K}$ 意义下，多项式 $ f(x) $ 的零点数，即满足 $ f(n) \equiv 0 \pmod{10^K} $ 的非负整数 $ n $ 的个数，其中 $ n $ 的范围为 $ 0 $ 至 $ 10^K - 1 $。

从标准输入以以下格式读取： > $ K $ $ S $

输出一个整数，表示满足 $ f(n) \equiv 0 \pmod{10^K} $ 的 $ 0 $ 至 $ 10^K - 1 $ 的整数 $ n $ 的个数。

- 所有输入均为整数 - $ 1 \leq K \leq 9 $ - $ 1 \leq |S| \leq 100 $ ### 示例解释 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} $ ### 示例解释 2 输入的多项式为 $ f(x) = \left(\left(\left(x\right)\right)^{234567890} \times 1^1 \times 1 + \left(x^2\right)^2\right) $。 ### 示例解释 3 输入的多项式为 $ f(x) = 50 + \left(2019 - x + \left(x^3 - x\right)^{2019}\right) \times x^1 $。 **本翻译由 AI 自动生成**