수식 채굴

다음 문법 규칙으로 정의되는, 시작 기호가 $E$인 산술 식을 생각하자. 산술 식은 한 자리 양의 정수, 덧셈 기호 +, 곱셈 기호 *, 괄호 (, )로 만들어진다.

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

이런 산술 식을 문자열로 볼 때, 그 부분 문자열(연속된 문자들의 나열)도 다시 산술 식이 될 수 있다. 정수 $n$과 산술 식을 나타내는 문자열 $s$가 주어질 때, 산술 식으로 읽을 수 있고 계산한 값이 $n$인 $s$의 부분 문자열의 개수를 구하라.

입력은 여러 데이터셋으로 이루어지며, 각 데이터셋은 다음 형식이다.

첫 줄에 목표 값 $n$이 주어진다. $1 \le n \le 10^9$이다. 둘째 줄에 문자열 $s$가 주어진다. $s$는 위 문법을 따르는 산술 식이다. $s$의 길이는 $2 \times 10^6$을 넘지 않고, $s$에 나오는 괄호의 중첩 깊이는 최대 1000이다. 입력의 끝은 0 한 줄로 표시된다. 모든 데이터셋에 걸친 $s$ 길이의 합은 $5 \times 10^6$을 넘지 않는다.

각 데이터셋마다 한 줄에 $s$의 부분 문자열 중 위 문법을 따르고 값이 $n$인 것의 개수를 출력한다. 같은 문자열이라도 위치가 다르면 따로 센다.