Expression Mining

Consider an arithmetic expression with start symbol $E$, defined by the following grammar. It is built from single-digit positive integers, the addition symbol +, the multiplication symbol *, and parentheses ( and ).

E ::= T | E '+' T
T ::= F | T '*' F
F ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '(' E ')'

When such an expression is viewed as a string, a substring (a contiguous sequence of characters) may again form an arithmetic expression. Given an integer $n$ and a string $s$ that represents an arithmetic expression, count the substrings of $s$ that can be read as arithmetic expressions whose computed value is $n$.

The input has multiple datasets, each in the following format.

The first line contains the target value $n$, where $1 \le n \le 10^9$. The second line contains the string $s$, an arithmetic expression that follows the grammar above. The length of $s$ is at most $2 \times 10^6$, and the nesting depth of parentheses in $s$ is at most 1000. The input ends with a line containing a single 0. The sum of the lengths of $s$ over all datasets is at most $5 \times 10^6$.

For each dataset, output on one line the number of substrings of $s$ that conform to the grammar and have value $n$. Identical substrings at different positions are counted separately.