#include <bits/stdc++.h>
using namespace std;
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&...args) {
  const char *comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
long long mod = 1e9 + 7;
void add(long long &a, long long b) {
  a += b;
  if (a >= mod) a -= mod;
  if (a < 0) a += mod;
}
long long mul(long long a, long long b) { return (a * b) % mod; }
long long mulmod(long long a, long long b, long long M) {
  if (M <= mod) return mul(a, b);
  long long res = 0;
  while (a > 0) {
    if (a & 1ll) {
      res += b;
      if (res >= M) res -= M;
    }
    a >>= 1;
    b <<= 1;
    if (b >= M) b -= M;
  }
  return res;
}
long long ffmod(long long b, long long exp, long long md = mod) {
  long long res = 1;
  while (exp) {
    if (exp & 1ll) res = (res * b) % md;
    b = (b * b) % md;
    exp /= 2ll;
  }
  return res;
}
const int N = 1000010;
const int M = 100010;
const int LN = 20;
const int NMOD = 2;
const long long m_1 = 1e9 + 7;
const long long m_2 = 1e9 + 9;
long long sel_mod[2] = {m_1, m_2};
long long sel_pow[2] = {29, 786433};
struct Hsh {
  string second;
  int n;
  long long mod[NMOD];
  long long power[N][NMOD], invpower[N][NMOD], pre[N][NMOD];
  Hsh(){};
  void init(const string &st1, long long *pw1 = sel_pow,
            long long *mod1 = sel_mod, int num = NMOD) {
    second = st1;
    for (int j = 0; j < num; j++) {
      mod[j] = mod1[j];
      power[0][j] = 1;
      power[1][j] = pw1[j];
      invpower[0][j] = 1;
      invpower[1][j] = ffmod(pw1[j], mod[j] - 2, mod[j]);
      for (int i = 2; i <= second.length(); i++) {
        power[i][j] = (power[i - 1][j] * pw1[j]) % mod[j];
        invpower[i][j] = (invpower[i - 1][j] * invpower[1][j]) % mod[j];
      }
      for (int i = 1; i < second.length(); i++) {
        pre[i][j] = (pre[i - 1][j] +
                     (1ll * (second[i] - 'a' + 1) * power[i][j]) % mod[j]) %
                    mod[j];
      }
    }
    n = num;
  }
  pair<long long, long long> get(int st, int len) {
    long long ans[n];
    for (int j = 0; j < n; j++) {
      long long cur = (pre[st + len - 1][j] - pre[st - 1][j] + mod[j]) % mod[j];
      cur = (cur * invpower[st - 1][j]) % mod[j];
      ans[j] = cur;
    }
    return make_pair(ans[0], ans[1]);
  }
  pair<long long, long long> getSub(int i, int j) { return get(i, j - i + 1); }
  pair<long long, long long> get(const string &s1) {
    long long hsh[n];
    for (int j = 0; j < n; j++) {
      hsh[j] = 0;
      for (int i = 1; i < s1.length(); i++) {
        hsh[j] = (hsh[j] + (power[i][j] * 1ll * (s1[i] - 'a' + 1)) % mod[j]) %
                 mod[j];
      }
    }
    return make_pair(hsh[0], hsh[1]);
  }
};
pair<long long, long long> dummy = make_pair(-1, -1);
struct stringHash {
  string second;
  Hsh pre, suf;
  stringHash(const string &s1) {
    second = s1;
    pre.init("#" + second);
    string t = second;
    reverse(t.begin(), t.end());
    suf.init("#" + t);
  }
  pair<long long, long long> getPre(int i) { return pre.get(1, i); }
  pair<long long, long long> getSuf(int i) {
    return suf.get(1, second.length() - i);
  }
  pair<long long, long long> getSub(int i, int j) { return pre.getSub(i, j); }
  pair<long long, long long> getRev(int i, int j) {
    return suf.getSub(second.length() - j, second.length() - i);
  }
};
string second, t;
Hsh m;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, i, j;
  cin >> second;
  cin >> t;
  second = "#" + second;
  t = "#" + t;
  int tlen = t.length() - 1;
  int slen = second.length() - 1;
  int numa = 0, numb = 0;
  for (i = 1; i <= slen; i++) {
    if (second[i] == '0')
      numa++;
    else
      numb++;
  }
  m.init(t);
  int ans = 0;
  for (i = 1; i <= tlen - 1; i++) {
    int lena = i;
    int fl = 0;
    long long tot = 1ll * numa * 1ll * lena;
    if (tlen - tot <= 0 || ((tlen - tot) % (1ll * numb) != 0)) continue;
    int lenb = (tlen - tot) / numb;
    int got0 = 0, got1 = 0;
    pair<long long, long long> a, b;
    int cur = 1;
    for (j = 1; j <= slen; j++) {
      if (second[j] == '0') {
        if (got0) {
          fl = (a != m.get(cur, lena));
        } else {
          a = m.get(cur, lena);
          got0 = 1;
        }
        cur += lena;
        if (fl) break;
      } else {
        if (got1) {
          fl = (b != m.get(cur, lenb));
        } else {
          b = m.get(cur, lenb);
          got1 = 1;
        }
        cur += lenb;
        if (fl) break;
      }
    }
    if (!fl && !(a == b && lena == lenb)) ans++;
  }
  cout << ans << "\n";
  return 0;
}

### Prompt

Your challenge is to write a cpp solution to the following problem:

One of Arkady's friends works at a huge radio telescope. A few decades ago the telescope has sent a signal s towards a faraway galaxy. Recently they've received a response t which they believe to be a response from aliens! The scientists now want to check if the signal t is similar to s.

The original signal s was a sequence of zeros and ones (everyone knows that binary code is the universe-wide language). The returned signal t, however, does not look as easy as s, but the scientists don't give up! They represented t as a sequence of English letters and say that t is similar to s if you can replace all zeros in s with some string r_0 and all ones in s with some other string r_1 and obtain t. The strings r_0 and r_1 must be different and non-empty.

Please help Arkady's friend and find the number of possible replacements for zeros and ones (the number of pairs of strings r_0 and r_1) that transform s to t.

Input

The first line contains a string s (2 ≤ |s| ≤ 10^5) consisting of zeros and ones — the original signal.

The second line contains a string t (1 ≤ |t| ≤ 10^6) consisting of lowercase English letters only — the received signal.

It is guaranteed, that the string s contains at least one '0' and at least one '1'.

Output

Print a single integer — the number of pairs of strings r_0 and r_1 that transform s to t.

In case there are no such pairs, print 0.

Examples

Input


01
aaaaaa


Output


4


Input


001
kokokokotlin


Output


2

Note

In the first example, the possible pairs (r_0, r_1) are as follows:

  * "a", "aaaaa" 
  * "aa", "aaaa" 
  * "aaaa", "aa" 
  * "aaaaa", "a" 



The pair "aaa", "aaa" is not allowed, since r_0 and r_1 must be different.

In the second example, the following pairs are possible: 

  * "ko", "kokotlin" 
  * "koko", "tlin" 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&...args) {
  const char *comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " : " << arg1 << " | ";
  __f(comma + 1, args...);
}
long long mod = 1e9 + 7;
void add(long long &a, long long b) {
  a += b;
  if (a >= mod) a -= mod;
  if (a < 0) a += mod;
}
long long mul(long long a, long long b) { return (a * b) % mod; }
long long mulmod(long long a, long long b, long long M) {
  if (M <= mod) return mul(a, b);
  long long res = 0;
  while (a > 0) {
    if (a & 1ll) {
      res += b;
      if (res >= M) res -= M;
    }
    a >>= 1;
    b <<= 1;
    if (b >= M) b -= M;
  }
  return res;
}
long long ffmod(long long b, long long exp, long long md = mod) {
  long long res = 1;
  while (exp) {
    if (exp & 1ll) res = (res * b) % md;
    b = (b * b) % md;
    exp /= 2ll;
  }
  return res;
}
const int N = 1000010;
const int M = 100010;
const int LN = 20;
const int NMOD = 2;
const long long m_1 = 1e9 + 7;
const long long m_2 = 1e9 + 9;
long long sel_mod[2] = {m_1, m_2};
long long sel_pow[2] = {29, 786433};
struct Hsh {
  string second;
  int n;
  long long mod[NMOD];
  long long power[N][NMOD], invpower[N][NMOD], pre[N][NMOD];
  Hsh(){};
  void init(const string &st1, long long *pw1 = sel_pow,
            long long *mod1 = sel_mod, int num = NMOD) {
    second = st1;
    for (int j = 0; j < num; j++) {
      mod[j] = mod1[j];
      power[0][j] = 1;
      power[1][j] = pw1[j];
      invpower[0][j] = 1;
      invpower[1][j] = ffmod(pw1[j], mod[j] - 2, mod[j]);
      for (int i = 2; i <= second.length(); i++) {
        power[i][j] = (power[i - 1][j] * pw1[j]) % mod[j];
        invpower[i][j] = (invpower[i - 1][j] * invpower[1][j]) % mod[j];
      }
      for (int i = 1; i < second.length(); i++) {
        pre[i][j] = (pre[i - 1][j] +
                     (1ll * (second[i] - 'a' + 1) * power[i][j]) % mod[j]) %
                    mod[j];
      }
    }
    n = num;
  }
  pair<long long, long long> get(int st, int len) {
    long long ans[n];
    for (int j = 0; j < n; j++) {
      long long cur = (pre[st + len - 1][j] - pre[st - 1][j] + mod[j]) % mod[j];
      cur = (cur * invpower[st - 1][j]) % mod[j];
      ans[j] = cur;
    }
    return make_pair(ans[0], ans[1]);
  }
  pair<long long, long long> getSub(int i, int j) { return get(i, j - i + 1); }
  pair<long long, long long> get(const string &s1) {
    long long hsh[n];
    for (int j = 0; j < n; j++) {
      hsh[j] = 0;
      for (int i = 1; i < s1.length(); i++) {
        hsh[j] = (hsh[j] + (power[i][j] * 1ll * (s1[i] - 'a' + 1)) % mod[j]) %
                 mod[j];
      }
    }
    return make_pair(hsh[0], hsh[1]);
  }
};
pair<long long, long long> dummy = make_pair(-1, -1);
struct stringHash {
  string second;
  Hsh pre, suf;
  stringHash(const string &s1) {
    second = s1;
    pre.init("#" + second);
    string t = second;
    reverse(t.begin(), t.end());
    suf.init("#" + t);
  }
  pair<long long, long long> getPre(int i) { return pre.get(1, i); }
  pair<long long, long long> getSuf(int i) {
    return suf.get(1, second.length() - i);
  }
  pair<long long, long long> getSub(int i, int j) { return pre.getSub(i, j); }
  pair<long long, long long> getRev(int i, int j) {
    return suf.getSub(second.length() - j, second.length() - i);
  }
};
string second, t;
Hsh m;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, i, j;
  cin >> second;
  cin >> t;
  second = "#" + second;
  t = "#" + t;
  int tlen = t.length() - 1;
  int slen = second.length() - 1;
  int numa = 0, numb = 0;
  for (i = 1; i <= slen; i++) {
    if (second[i] == '0')
      numa++;
    else
      numb++;
  }
  m.init(t);
  int ans = 0;
  for (i = 1; i <= tlen - 1; i++) {
    int lena = i;
    int fl = 0;
    long long tot = 1ll * numa * 1ll * lena;
    if (tlen - tot <= 0 || ((tlen - tot) % (1ll * numb) != 0)) continue;
    int lenb = (tlen - tot) / numb;
    int got0 = 0, got1 = 0;
    pair<long long, long long> a, b;
    int cur = 1;
    for (j = 1; j <= slen; j++) {
      if (second[j] == '0') {
        if (got0) {
          fl = (a != m.get(cur, lena));
        } else {
          a = m.get(cur, lena);
          got0 = 1;
        }
        cur += lena;
        if (fl) break;
      } else {
        if (got1) {
          fl = (b != m.get(cur, lenb));
        } else {
          b = m.get(cur, lenb);
          got1 = 1;
        }
        cur += lenb;
        if (fl) break;
      }
    }
    if (!fl && !(a == b && lena == lenb)) ans++;
  }
  cout << ans << "\n";
  return 0;
}

```