Consider an arithmetic expression built by combining single-digit positive integers
with addition symbols `+`, multiplication symbols `*`,
and parentheses `(` `)`,
defined by the following grammar rules with the start symbol `E`.

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

When such an arithmetic expression is viewed as a string,
its substring, that is, a contiguous sequence of characters within the string,
may again form an arithmetic expression.
Given an integer *n* and a string *s* representing an arithmetic expression,
let us count the number of its substrings that can be read as arithmetic expressions
with values computed equal to *n*.

The input consists of multiple datasets, each in the following format.

n

s

A dataset consists of two lines.
In the first line, the target value *n* is given.
*n* is an integer satisfying 1 ≤ *n* ≤ 10^{9}.
The string *s* given in the second line
is an arithmetic expression conforming to the grammar defined above.
The length of *s* does not exceed 2×10^{6}.
The nesting depth of the parentheses in the string is at most 1000.

The end of the input is indicated by a line containing a single zero.
The sum of the lengths of *s*
in all the datasets does not exceed 5×10^{6}.

For each dataset, output in one line the number of substrings of *s* that
conform to the above grammar and have the value *n*.
The same sequence of characters appearing at different positions should be counted separately.

3 (1+2)*3+3 2 1*1*1+1*1*1 587 1*(2*3*4)+5+((6+7*8))*(9) 0

4 9 2

Source: ACM International Collegiate Programming Contest
, Japan Domestic Contest, Yokohama, Japan, 2018-07-6

https://icpc.iisf.or.jp/2018-yokohama/

https://icpc.iisf.or.jp/2018-yokohama/