Expression Mining

時間制限 : 8 sec, メモリ制限 : 262144 KB
英語版はこちら

数式探し

一桁の正整数を加算記号 + と乗算記号 * と括弧 ( ) とで組み合わせた数式を考える.数式は,以下の文法規則と開始記号 E で定義される.

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

このような数式を文字列として見たとき,その部分文字列, つまりその文字列中の連続する文字の並びも,また数式として解釈できることがある. 整数 n と数式を表す文字列 s が与えられたとき, s の部分文字列のうち,数式として解釈することができ, 計算すると値が n と一致するものがいくつあるか数えてみよう.

Input

入力は複数のデータセットからなる. 各データセットは次の形式で表される.

n
s

データセットは 2 行からなる. 1 行目には目標値 n が与えられる. n は整数であり,1 ≤ n ≤ 109 が成り立つ. 2 行目に与えられる文字列 s は上述の文法に従う数式である. s の長さは 2×106 を超えない. また,s の括弧の入れ子の深さは最大で 1000 段である.

入力の終わりはゼロひとつからなる行で表される. 全データセットの s の長さの合計は 5×106 を超えない.

Output

各データセットについて,s の部分文字列のうち, 上記の文法に従っていて数式として計算すると値が n になるものの個数を一行に出力せよ. 同じ文字の並びでも異なる場所にあるものは別々に数えよ.

Sample Input

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

Output for the Sample Input

4
9
2

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Yokohama, Japan, 2018-07-6
https://icpc.iisf.or.jp/2018-yokohama/