Problem Description

A polynomial $ f(x) $ in $ x $ is given as a string $ S $. Here, $ S $ is represented by the <expr> symbol in the following BNF notation:

<expr> ::= <term> | <expr> "+" <term> | <expr> "-" <term> <term> ::= <factor> | <term> "*" <factor> <factor> ::= <value> | <value> "^" <number> <value> ::= <number> | "x" | "(" <expr> ")" <number> ::= integer between $ 1 $ and $ 10^9 $ (exclusive), with leading zeros omitted

The symbols represent the following meanings:

• x: $ x $
• +: addition
• -: subtraction
• *: multiplication, which is computed before addition + or subtraction -
• ^: exponentiation, which is computed before addition +, subtraction -, or multiplication *

For example, the following strings can be represented by the <expr> symbol:

• 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$

The following strings cannot be represented by the <expr> symbol:

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

Find the number of zeros of $ f(x) $ modulo $ 10^K $, i.e., the number of integers $ n $ between $ 0 $ and $ 10^K $ (exclusive) that satisfy $f(n)\ \equiv\ 0\ \pmod{10^K}$.

Input Format

The input is given from the standard input in the following format:

$ K $ $ S $

Output Format

Output the number of integers $ n $ between $ 0 $ and $ 10^K $ (exclusive) that satisfy $f(n)\ \equiv\ 0\ \pmod{10^K}$.

Sample Input and Output

Sample Input #1

2
x^2-x

Sample Output #1

4

Sample Input #2

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

Sample Output #2

1000128

Sample Input #3

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

Sample Output #3

6

Notes/Hints

Constraints

• All inputs are integers.
• $1\ \leq\ K\ \leq\ 9$
• $1\ \leq\ |S|\ \leq\ 100$

Sample Explanation 1

• The input polynomial represents $f(x)\ =\ x^2\ -\ x$.
• The following values of $ n $ satisfy the condition: $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

• The input polynomial represents $f(x)\ =\ \left(\left(\left(x\right)\right)^{234567890}\ \times\ 1^1\ \times\ 1+\left(x^2\right)^2\right)$.

Sample Explanation 3

• The input polynomial represents $f(x)\ =\ 50+\left(2019-x+\left(x^3-x\right)^{2019}\right)\ \times\ x^1$.

见题面 Input 部分

见题面 Output 部分