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 自动生成