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 Int = long long;

template<typename T,T MOD = 1000000007>
struct Mint{
  static constexpr T mod = MOD;
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

  Mint pow(long long k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1) res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }

  static Mint add_identity(){return Mint(0);}
  static Mint mul_identity(){return Mint(1);}

  Mint inv(){return pow(MOD-2);}

  Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
  Mint& operator/=(Mint a){return (*this)*=a.inv();}

  Mint operator+(Mint a) const{return Mint(v)+=a;};
  Mint operator-(Mint a) const{return Mint(v)-=a;};
  Mint operator*(Mint a) const{return Mint(v)*=a;};
  Mint operator/(Mint a) const{return Mint(v)/=a;};

  Mint operator-() const{return v?Mint(MOD-v):Mint(v);}

  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}
  bool operator <(const Mint a)const{return v <a.v;}

  static Mint comb(long long n,int k){
    Mint num(1),dom(1);
    for(int i=0;i<k;i++){
      num*=Mint(n-i);
      dom*=Mint(i+1);
    }
    return num/dom;
  }
};
template<typename T,T MOD> constexpr T Mint<T, MOD>::mod;
template<typename T,T MOD>
ostream& operator<<(ostream &os,Mint<T, MOD> m){os<<m.v;return os;}

//BEGIN CUT HERE
template<typename T,typename M1,typename M2,typename M3>
struct PolynomialHash{
  using V = tuple<M1, M2, M3>;
  const T BASE = 1777771;

  vector<M1> po1,op1;
  vector<M2> po2,op2;
  vector<M3> po3,op3;

  template<typename M>
  void init(int n,vector<M>& po,vector<M>& op){
    po.assign(n+1,1);
    op.assign(n+1,1);
    M x(BASE);
    M y=M(x).inv();
    for(int i=1;i<=(int)n;i++) po[i]=po[i-1]*x;
    for(int i=1;i<=(int)n;i++) op[i]=op[i-1]*y;
  }

  PolynomialHash(size_t n){
    init(n,po1,op1);
    init(n,po2,op2);
    init(n,po3,op3);
  }

  V build(const vector<T> &v){
    int n=v.size();
    M1 r1;M2 r2;M3 r3;
    for(int i=0;i<n;i++){
      r1+=M1(v[i])*po1[i];
      r2+=M2(v[i])*po2[i];
      r3+=M3(v[i])*po3[i];
    }
    return V(r1,r2,r3);
  }

  V add(const V &a,const V &b){
    M1 a1=get<0>(a),b1=get<0>(b);
    M2 a2=get<1>(a),b2=get<1>(b);
    M3 a3=get<2>(a),b3=get<2>(b);
    return V(a1+b1,a2+b2,a3+b3);
  }

  V sub(const V &a,const V &b){
    M1 a1=get<0>(a),b1=get<0>(b);
    M2 a2=get<1>(a),b2=get<1>(b);
    M3 a3=get<2>(a),b3=get<2>(b);
    return V(a1-b1,a2-b2,a3-b3);
  }

  V mul(const V &a,const V &b){
    M1 a1=get<0>(a),b1=get<0>(b);
    M2 a2=get<1>(a),b2=get<1>(b);
    M3 a3=get<2>(a),b3=get<2>(b);
    return V(a1*b1,a2*b2,a3*b3);
  }

  V inv(const V &a){
    M1 a1;M2 a2;M3 a3;
    tie(a1,a2,a3)=a;
    return V(a1.inv(),a2.inv(),a3.inv());
  }

  V term(size_t x,T k){
    M1 a1=po1[x]*M1((long long)k);
    M2 a2=po2[x]*M2((long long)k);
    M3 a3=po3[x]*M3((long long)k);
    return V(a1,a2,a3);
  }

};
//END CUT HERE

signed CODEFLYER2018_F(){
  const int MAX = 2020;
  using BS = bitset<MAX>;

  int h,w,q;
  scanf("%d %d %d",&h,&w,&q);
  vector<string> s(h);
  char buf[MAX];
  for(int i=0;i<h;i++){
    scanf("%s",buf);
    s[i]=string(buf);
  }

  vector<BS> rs(h),cs(w);
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      rs[i][j]=(s[i][j]=='#');
      cs[j][i]=(s[i][j]=='#');
    }
  }

  auto conv=
    [&](BS &v,int k){
      vector<int> a(k);
      for(int i=0;i<k;i++) a[i]=v[i];
      return a;
    };

  using M1 = Mint<int, int(1e9+7)>;
  using M2 = Mint<int, int(1e9+9)>;
  using M3 = Mint<int, int(1e8+7)>;

  PolynomialHash<int, M1, M2, M3> ph(MAX);
  using V = decltype(ph)::V;

  vector<V> vrs(h),vcs(w);
  vector<int> tmp(w,1);
  V ri=ph.build(tmp);
  tmp.assign(h,1);
  V ci=ph.build(tmp);

  for(int i=0;i<h;i++){
    auto v=conv(rs[i],w);
    vrs[i]=ph.build(v);
    if(rs[i][0]) vrs[i]=ph.sub(ri,vrs[i]);
  }

  for(int j=0;j<w;j++){
    auto v=conv(cs[j],h);
    vcs[j]=ph.build(v);
    if(cs[j][0]) vcs[j]=ph.sub(ci,vcs[j]);
  }

  map<V, set<int> > mrs, mcs;
  for(int i=0;i<h;i++) mrs[vrs[i]].emplace(i);
  for(int j=0;j<w;j++) mcs[vcs[j]].emplace(j);

  auto check=
    [&](){
      int a1=-1,b1=-1,c1=-1,d1=-1;
      int a2=-1,b2=-1,c2=-1,d2=-1;

      int A,B,C,D;

      {
        auto latte=mrs.begin();
        set<int> &s=latte->second;
        latte++;
        set<int> &t=latte->second;
        if(*--s.end()-*s.begin()+1==(int)s.size()){
          a1=*s.begin();
          b1=*--s.end();
        }
        if(*--t.end()-*t.begin()+1==(int)t.size()){
          a2=*t.begin();
          b2=*--t.end();
        }
        A=*s.begin();
        B=*t.begin();
      }
      if(a1<0&&a2<0){
        puts("No");
        return;
      }

      {
        auto latte=mcs.begin();
        set<int> &s=latte->second;
        latte++;
        set<int> &t=latte->second;
        if(*--s.end()-*s.begin()+1==(int)s.size()){
          c1=*s.begin();
          d1=*--s.end();
        }
        if(*--t.end()-*t.begin()+1==(int)t.size()){
          c2=*t.begin();
          d2=*--t.end();
        }
        C=*s.begin();
        D=*t.begin();
      }

      if(c1<0&&c2<0){
        puts("No");
        return;
      }

      {
        int flg=0;
        if(~c1){
          BS r=rs[A]^rs[B];
          r>>=c1;
          int k=r.count();
          r>>=(d1-c1+1);
          k-=r.count();
          flg|=(d1-c1+1)==k;
        }
        if(~c1){
          BS r=rs[A]^~rs[B];
          r>>=c1;
          int k=r.count();
          r>>=(d1-c1+1);
          k-=r.count();
          flg|=(d1-c1+1)==k;
        }
        if(~c2){
          BS r=rs[A]^rs[B];
          r>>=c2;
          int k=r.count();
          r>>=(d2-c2+1);
          k-=r.count();
          flg|=(d2-c2+1)==k;
        }
        if(~c2){
          BS r=rs[A]^~rs[B];
          r>>=c2;
          int k=r.count();
          r>>=(d2-c2+1);
          k-=r.count();
          flg|=(d2-c2+1)==k;
        }
        if(!flg){
          puts("No");
          return;
        }
      }

      {
        int flg=0;
        if(~a1){
          BS r=cs[C]^cs[D];
          r>>=a1;
          int k=r.count();
          r>>=(b1-a1+1);
          k-=r.count();
          flg|=(b1-a1+1)==k;
        }
        if(~a1){
          BS r=cs[C]^~cs[D];
          r>>=a1;
          int k=r.count();
          r>>=(b1-a1+1);
          k-=r.count();
          flg|=(b1-a1+1)==k;
        }
        if(~a2){
          BS r=cs[C]^cs[D];
          r>>=a2;
          int k=r.count();
          r>>=(b2-a2+1);
          k-=r.count();
          flg|=(b2-a2+1)==k;
        }
        if(~a2){
          BS r=cs[C]^~cs[D];
          r>>=a2;
          int k=r.count();
          r>>=(b2-a2+1);
          k-=r.count();
          flg|=(b2-a2+1)==k;
        }
        if(!flg){
          puts("No");
          return;
        }
      }

      puts("Yes");
    };

  auto calc=
    [&](){
      if(mrs.size()>2u||mcs.size()>2u){
        puts("No");
        return;
      }
      if(mrs.size()==1u||mcs.size()==1u){
        puts("Yes");
        return;
      }

      if(mrs.size()==2u||mcs.size()==2u){
        check();
        return;
      }
      puts("No");
    };

  calc();

  for(int i=1;i<q;i++){
    int r,c;
    scanf("%d %d",&r,&c);
    r--;c--;

    mrs[vrs[r]].erase(r);
    if(mrs[vrs[r]].empty()) mrs.erase(vrs[r]);
    mcs[vcs[c]].erase(c);
    if(mcs[vcs[c]].empty()) mcs.erase(vcs[c]);

    if(rs[r][0]) vrs[r]=ph.sub(ri,vrs[r]);
    if(cs[c][0]) vcs[c]=ph.sub(ci,vcs[c]);

    if(rs[r][c]){
      vrs[r]=ph.sub(vrs[r],ph.term(c,1));
      vcs[c]=ph.sub(vcs[c],ph.term(r,1));
    }else{
      vrs[r]=ph.add(vrs[r],ph.term(c,1));
      vcs[c]=ph.add(vcs[c],ph.term(r,1));
    }

    rs[r][c].flip();
    cs[c][r].flip();

    if(rs[r][0]) vrs[r]=ph.sub(ri,vrs[r]);
    if(cs[c][0]) vcs[c]=ph.sub(ci,vcs[c]);

    mrs[vrs[r]].emplace(r);
    mcs[vcs[c]].emplace(c);

    calc();
  }

  return 0;
}
/*
  verified on 2019/10/15
  https://atcoder.jp/contests/bitflyer2018-final/tasks/bitflyer2018_final_f
*/


using M1 = Mint<int, int(1e9+7)>;
using M2 = Mint<int, int(1e9+9)>;
using M3 = Mint<int, int(1e8+7)>;
PolynomialHash<int, M1, M2, M3> ph(100);
using V = decltype(ph)::V;

vector<vector<V> > vs;
vector<vector<vector<V> > > vm;

V expr(string &s,int &p,int d);
V term(string &s,int &p,int d);
V factor(string &s,int &p,int d);
V number(string &s,int &p);

V expr(string &s,int &p,int d){
  V res=term(s,p,d);
  vs[d].emplace_back(res);
  while(p<(int)s.size()){
    if(s[p]=='+'){
      p++;
      V b=term(s,p,d);
      vs[d].emplace_back(b);
      res=ph.add(res,b);
      continue;
    }
    break;
  }
  vs[d].emplace_back(0,0,0);
  vm[d].emplace_back();
  return res;
}

V term(string &s,int &p,int d){
  V res=factor(s,p,d);
  vm[d].emplace_back();
  vm[d].back().emplace_back(res);
  while(p<(int)s.size()){
    if(s[p]=='*'){
      p++;
      V b=factor(s,p,d);
      vm[d].back().emplace_back(b);
      res=ph.mul(res,b);
      continue;
    }
    break;
  }
  return res;
}

V factor(string &s,int &p,int d){
  if(s[p]=='('){
    p++;
    V res=expr(s,p,d+1);
    assert(s[p]==')');
    p++;
    return res;
  }
  return number(s,p);
}

V number(string &s,int &p){
  int k=s[p++]-'0';
  return V(k,k,k);
}

signed AOJ_1630(){
  using ll = long long;

  int n;
  while(cin>>n,n){
    string s;
    cin>>s;
    vs.assign(1010,vector<V>());
    vm.assign(1010,vector<vector<V> >());

    V nv=ph.term(0,n);

    int p=0;
    expr(s,p,0);
    ll ans=0;

    for(int i=0;i<1010;i++){
      auto &v=vs[i];
      if(v.empty()) continue;
      map<V, ll> dp;
      V uku(0,0,0);
      dp[uku]++;
      for(int j=0;j<(int)v.size();j++){
        if(v[j]==V(0,0,0)){
          dp.clear();
          uku=V(0,0,0);
          dp[uku]++;
          continue;
        }
        V malta(1,1,1);
        for(int k=0;k<(int)vm[i][j].size();k++){
          malta=ph.mul(malta,vm[i][j][k]);
          ans+=dp[ph.sub(ph.add(uku,malta),nv)];
        }

        map<V, ll> dp2;
        malta=V(1,1,1);
        dp2[ph.mul(malta,nv)]++;
        for(int k=1;k<(int)vm[i][j].size();k++){
          malta=ph.mul(malta,vm[i][j][k]);
          ans+=dp2[malta];
          dp2[ph.mul(malta,nv)]++;
        }

        uku=ph.add(uku,v[j]);
        malta=V(1,1,1);
        for(int k=0;k+1<(int)vm[i][j].size();k++){
          malta=ph.mul(malta,vm[i][j][k]);
          dp[ph.sub(uku,ph.mul(v[j],ph.inv(malta)))]++;
        }
        dp[uku]++;
      }
    }

    cout<<ans<<endl;
  }
  return 0;
}


//INSERT ABOVE HERE
signed main(){
  //CODEFLYER2018_F();
  AOJ_1630();
  return 0;
}