数式探し

一桁の正整数を加算記号 + と乗算記号 * と括弧 ( ) とで組み合わせた数式を考える．数式は，以下の文法規則と開始記号 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 ≤ 10⁹ が成り立つ． 2 行目に与えられる文字列 s は上述の文法に従う数式である． s の長さは 2×10⁶ を超えない． また，s の括弧の入れ子の深さは最大で 1000 段である．

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

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

---