Problem: Expression Mining

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.

Input

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 ≤ 109. 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×106. 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×106.

Output

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.

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






Example

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

4
9
2

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

constexpr int mod = 1e9 + 7;

#define dump(x) ([&](){auto ___val = (x); cout << #x << " = " << (___val) << endl; })();
// #define dump(x) ;


template<class T>
ostream&operator<<(ostream &os, vector<T>v) {
  os << "{";
  for(size_t i = 0; i < v.size(); i++) os << v[i] << ", ";
  os << "}";
  return os;
}

template<class T, class U>
ostream&operator<<(ostream &os, pair<T, U>v) {
  os << "(" << v.first << " , " << v.second << ")";
  return os;
}

template<class T, class U>
ostream&operator<<(ostream &os, map<T, U>v) {
  os << "(map: \n";
  for(auto e : v) os << e << ", \n";
  os << ")";
  return os;
}

template<class T>
ostream&operator<<(ostream &os, set<T>v) {
  os << "(set: \n";
  for(auto e : v) os << e << ", \n";
  os << ")";
  return os;
}

using Vec = vector<int>;
using Mat = vector<Vec>;

ll modpow(ll x, ll k, ll mod) {
  x %= mod;
  ll r = 1;
  assert(k >= 0);
  while(k) {
    if(k & 1) r = r * x % mod;
    x = x * x % mod;
    k >>= 1;
  }
  return r;
}

ll toint(string s) {
  ll res = 0;
  int n = s.size();
  for(int i = 0; i < n; i++) res |= (ll(s[n - 1 - i] - '0')) << i;
  return res;
}

string tostr(ll x, int n) {
  string res = "";
  for(int i = 0; i < n; i++) {
    res += '0' + ((x >> i) & 1);
  }
  reverse(begin(res), end(res));
  return res;
}

bool mul_OF(ll a, ll b) {
  // a * b > 4e18
  // a > floor(4e18 / b)
  return a > ll(3e18) / b;
}


enum NodeType {
  Add,
  Mul,
  Val,
};

constexpr ll inf = 1e9 + 100;

struct Node {
  int type;
  ll val; // 上限を適当につける
  vector<Node*> child;
  Node *parent = 0;
  ll op(ll x, ll y) {
    assert(type == Add || type == Mul);
    if(type == Add) return min(x + y, inf);
    else return min(x * y, inf);
  }
  ll calc() {
    if(type == Val) return val;
    val = type == Add ? 0 : 1;
    assert(child.size());
    for(auto c: child) {
      ll x = c->calc();
      val = op(val, x);
    }
    return val;
  }
  void addChild(Node* p) {
    child.push_back(p);
    p->parent = this;
  }
  void dfs(int n, ll & ans) {
    for(auto c : child) c->dfs(n, ans);
    if(type == Add) {
      int l1 = 0, l2 = 0;
      int r1 = 0, r2 = 0;

      ll now = 0;
      int cntOneR = 0;

      while(l1 < child.size()) {

        // n 以上になるまで右を伸ばし続ける

        while((r1 < child.size() && now < n) || make_pair(r1, r2) == make_pair(l1, l2)) {

          if(r2 == 0 && l1 + 1 == r1) {
            now = child.at(l1)->getRight(l2);
          }

          if(r1 == l1) {
            if(now == 0) now = 1;
            assert(!mul_OF(now, child.at(r1)->child.at(r2)->val));
            now *= child.at(r1)->child.at(r2)->val;
          } else {
            now -= child.at(r1)->getLeft(r2 - 1 + 1);
            now += child.at(r1)->getLeft(r2 + 1); // 左 r2 + 1 個の積をもらう
          }
          cntOneR = child.at(r1)->cntOneRight(r2 + 1);

          r2++;
          if(r2 >= child.at(r1)->child.size()) r1++, r2 = 0;
        }

        if(now == n) {
          ans += cntOneR + 1;
        }

        // 左をいっこ縮める

        if(l1 == r1 || (r2 == 0 && l1 + 1 == r1)) { /// 右側の条件も大事
          now /= child.at(l1)->child.at(l2)->val;
          if((l2 + 1) % child.at(l1)->child.size() == r2) now = 0;
        } else {
          now -= child.at(l1)->getRight(l2);
          now += child.at(l1)->getRight(l2 + 1);
        }

        l2++;
        if(l2 >= child.at(l1)->child.size()) l1++, l2 = 0;

        if(l2 == 0 && (l1 == r1 || (l1 + 1 == r1 && r2 == 0))) { ///// この右側の条件も大事
          int f = r2;
          if(l1 + 1 == r1 && r2 == 0) f = child.at(l1)->child.size(); /// ちゃんと一周するように
          if(f == 0) {
            now = 0;
          } else {
            now = 1;
            for(int i = 0; i < f; i++){
              assert(!mul_OF(now, child.at(l1)->child.at(i)->val));
              now *= child.at(l1)->child.at(i)->val;
            }
          }
        }
      }
    }
  }
  
  vector<ll> lsum;
  // i 未満のchildのvalの積
  ll getLeft(int i) {
    assert(type == Mul);
    if(lsum.size() == 0) {
      lsum.resize(child.size() + 1);
      lsum[0] = 1;
      for(int i = 0; i < child.size(); i++) lsum[i+1] = op(lsum[i], child[i]->val);

      lsum[0] = 0;
    }

    return lsum.at(i);
  }

  vector<int> oneR;
  // i 以上に1が何回連続してあらわれるか
  ll cntOneRight(int i) {
    assert(type == Mul);
    if(oneR.size() == 0) {
      int m = child.size(); 
      oneR.resize(m+1);
      oneR[m] = 0;
      for(int i = m - 1; i >= 0; i--) {
        if(child[i]->val != 1) oneR[i] = 0;
        else oneR[i] = oneR[i+1] + 1;
      }
    }

    return oneR.at(i);
  }


  vector<ll> rsum;
  // i以上のchildのvalの積
  ll getRight(int i) {
    assert(type == Mul);
    if(rsum.size() == 0) {
      int m = child.size();
      rsum.resize(m + 1);
      rsum[m] = 1;
      for(int i = m - 1; i >= 0; i--) rsum[i] = op(rsum[i+1], child[i]->val);

      rsum[m] = 0;
    }

    return rsum.at(i);
  }
};

Node* makeAdd() {
  Node* p = new Node;
  p->type = Add;
  return p;
}

Node* makeMul() {
  Node* p = new Node;
  p->type = Mul;
  return p;
}

Node* makeVal(int val) {
  Node* p = new Node;
  p->type = Val;
  p->val = val;
  return p;
}


// |
// - +
//   - *
//     - 3
//     - 2
//   - 1
//   - 2
//   - *
//     - +
//       - 3
//       - 1
//     - 3
//     - 2
//   - 3

// * -> + においてかならず括弧が必要になる

int main() {
  ios::sync_with_stdio(0), cin.tie(0);

  int ccc = 0;
  while(1) {
    ccc++;
    int n;
    cin >> n;
    if(!n) break;
    string s;
    cin >> s;
    
    // 構文解析

    // 括弧はすべて外して，どこにあったか，だけ記録しておく
    
    ll ans = 0;

    Node * t = makeAdd();
    Node * nxt = makeMul();
    t->addChild(nxt);

    for(char c : s) {
      // dump(c);
      switch(c) {
        case '(':
          {
            Node * u = makeAdd();
            nxt->addChild(u);
            t = u;
            nxt = makeMul();
            t->addChild(nxt);
            break;
          }
        case ')':
          {
            assert(t);
            assert(t->parent);
            assert(t->parent->parent);

            t = t->parent->parent;
            nxt = t->child.back();

            assert(nxt);
            break;
          }
        case '+':
          {
            nxt = makeMul();
            t->addChild(nxt);
            break;
          }
        case '*':
          {
            break;
          }
        default:
          {
            int x = c - '0';
            nxt->addChild(makeVal(x));
            break;
          }
      }
    }

    t->calc();

    // 各プラスノードについて，しゃくとり法を行う
    
    t->dfs(n, ans);

    cout << ans << "\n";
  }
}

// a * b * c
// a + b + c
// (a + b + c)
// ((a + b + c))

// プラスのノードでは，その全体が目的の値になっているかを確認する
//    - うまく, 他のパターンの一部にできた
// 1 がその後にいくつ続いているか，という情報がほしい