#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};
long long power[N][NMOD], invpower[N][NMOD], mods[NMOD];
void pre(long long *pw1 = sel_pow, long long *mod1 = sel_mod, int num = NMOD) {
  for (int j = 0; j < NMOD; j++) {
    mods[j] = mod1[j];
    power[0][j] = 1;
    power[1][j] = pw1[j];
    invpower[0][j] = 1;
    invpower[1][j] = ffmod(pw1[j], mods[j] - 2, mods[j]);
    for (int i = 2; i < N; i++) {
      power[i][j] = (power[i - 1][j] * pw1[j]) % mods[j];
      invpower[i][j] = (invpower[i - 1][j] * invpower[1][j]) % mods[j];
    }
  }
}
struct Hsh {
  string second;
  int n;
  vector<long long> pre[NMOD];
  Hsh(){};
  void init(const string &st1) {
    second = st1;
    for (int j = 0; j < NMOD; j++) {
      pre[j].resize(second.length() + 2);
      for (int i = 1; i < second.length(); i++) {
        pre[j][i] = (pre[j][i - 1] +
                     (1ll * (second[i] - 'a' + 1) * power[i][j]) % mods[j]) %
                    mods[j];
      }
    }
    n = NMOD;
  }
  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[j][st + len - 1] - pre[j][st - 1] + mods[j]) % mods[j];
      cur = (cur * invpower[st - 1][j]) % mods[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)) % mods[j]) %
                 mods[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 a;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m, i, j, k, x, q;
  cin >> second;
  cin >> t;
  pre();
  second = "#" + second;
  t = "#" + t;
  a.init(t);
  int ones = second.length() - 1;
  n = t.length() - 1;
  int zero = 0;
  for (i = 1; i <= second.length() - 1; i++)
    if (second[i] == '0') zero++;
  ones -= zero;
  int cnt = 0;
  for (int len = 1; len < t.length() - 1; len++) {
    long long tot = 1ll * len * zero;
    if (tot >= n) break;
    int rem = (n - tot);
    if (rem % ones) continue;
    int onelen = rem / ones;
    int fl = 0, cur = 0;
    pair<long long, long long> hsh0 = dummy, hsh1 = dummy, hsh;
    for (i = 1; i <= second.length() - 1; i++) {
      if (second[i] == '0') {
        hsh = a.get(cur + 1, len);
        cur += len;
        if (hsh0 == dummy || hsh0 == hsh)
          hsh0 = hsh;
        else {
          fl = 1;
          break;
        }
      } else {
        hsh = a.get(cur + 1, onelen);
        cur += onelen;
        if (hsh1 == dummy || hsh1 == hsh)
          hsh1 = hsh;
        else {
          fl = 1;
          break;
        }
      }
    }
    if (!fl && hsh0 != hsh1) cnt++;
  }
  cout << cnt << "\n";
  return 0;
}

### Prompt

Please create a solution in cpp 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};
long long power[N][NMOD], invpower[N][NMOD], mods[NMOD];
void pre(long long *pw1 = sel_pow, long long *mod1 = sel_mod, int num = NMOD) {
  for (int j = 0; j < NMOD; j++) {
    mods[j] = mod1[j];
    power[0][j] = 1;
    power[1][j] = pw1[j];
    invpower[0][j] = 1;
    invpower[1][j] = ffmod(pw1[j], mods[j] - 2, mods[j]);
    for (int i = 2; i < N; i++) {
      power[i][j] = (power[i - 1][j] * pw1[j]) % mods[j];
      invpower[i][j] = (invpower[i - 1][j] * invpower[1][j]) % mods[j];
    }
  }
}
struct Hsh {
  string second;
  int n;
  vector<long long> pre[NMOD];
  Hsh(){};
  void init(const string &st1) {
    second = st1;
    for (int j = 0; j < NMOD; j++) {
      pre[j].resize(second.length() + 2);
      for (int i = 1; i < second.length(); i++) {
        pre[j][i] = (pre[j][i - 1] +
                     (1ll * (second[i] - 'a' + 1) * power[i][j]) % mods[j]) %
                    mods[j];
      }
    }
    n = NMOD;
  }
  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[j][st + len - 1] - pre[j][st - 1] + mods[j]) % mods[j];
      cur = (cur * invpower[st - 1][j]) % mods[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)) % mods[j]) %
                 mods[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 a;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m, i, j, k, x, q;
  cin >> second;
  cin >> t;
  pre();
  second = "#" + second;
  t = "#" + t;
  a.init(t);
  int ones = second.length() - 1;
  n = t.length() - 1;
  int zero = 0;
  for (i = 1; i <= second.length() - 1; i++)
    if (second[i] == '0') zero++;
  ones -= zero;
  int cnt = 0;
  for (int len = 1; len < t.length() - 1; len++) {
    long long tot = 1ll * len * zero;
    if (tot >= n) break;
    int rem = (n - tot);
    if (rem % ones) continue;
    int onelen = rem / ones;
    int fl = 0, cur = 0;
    pair<long long, long long> hsh0 = dummy, hsh1 = dummy, hsh;
    for (i = 1; i <= second.length() - 1; i++) {
      if (second[i] == '0') {
        hsh = a.get(cur + 1, len);
        cur += len;
        if (hsh0 == dummy || hsh0 == hsh)
          hsh0 = hsh;
        else {
          fl = 1;
          break;
        }
      } else {
        hsh = a.get(cur + 1, onelen);
        cur += onelen;
        if (hsh1 == dummy || hsh1 == hsh)
          hsh1 = hsh;
        else {
          fl = 1;
          break;
        }
      }
    }
    if (!fl && hsh0 != hsh1) cnt++;
  }
  cout << cnt << "\n";
  return 0;
}

```