#include <bits/stdc++.h>
using namespace std;
template <typename T>
bool uax(T &a, const T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool uin(T &a, const T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &p) {
  in >> p.first >> p.second;
  return in;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &out, pair<T1, T2> &p) {
  out << p.first << ' ' << p.second;
  return out;
}
const long long MOD1 = 1e9 + 7, MOD2 = 1e9 + 9, P1 = 29, P2 = 31;
const int N = 2000005;
long long val(char x) { return (x - 'a') + 1; }
vector<pair<long long, long long>> poww(N);
struct Hash {
  long long h1, h2;
  Hash() {}
  Hash(long long h1_, long long h2_) {
    h1 = h1_;
    h2 = h2_;
  }
  Hash operator*(long long ind) {
    return Hash((h1 * poww[ind].first) % MOD1, (h2 * poww[ind].second) % MOD2);
  }
  bool operator==(Hash q) { return (h1 == q.h1 && h2 == q.h2); }
  Hash operator-(Hash q) {
    return Hash((h1 - q.h1 + MOD1) % MOD1, (h2 - q.h2 + MOD2) % MOD2);
  }
  Hash operator+(Hash q) {
    return Hash((h1 + q.h1) % MOD1, (h2 + q.h2) % MOD2);
  }
};
long long n;
string s, t;
vector<Hash> v;
long long ts, ss;
void precalc() {
  poww[0] = make_pair(1, 1);
  for (long long i = 1; i < N; i++) {
    poww[i] = make_pair((poww[i - 1].first * P1) % MOD1,
                        (poww[i - 1].second * P2) % MOD2);
  }
}
void build(string &s, vector<Hash> &h) {
  h.assign(s.size(), Hash());
  h[0] = Hash(val(s[0]), val(s[0]));
  for (long long i = 1; i < s.size(); i++) {
    h[i] = Hash((h[i - 1].h1 * P1 + val(s[i])) % MOD1,
                (h[i - 1].h2 * P2 + val(s[i])) % MOD2);
  }
  return;
}
Hash get_h(long long l, long long r, vector<Hash> &h) {
  if (l) {
    return h[r] - h[l - 1] * (r - l + 1);
  }
  return h[r];
}
bool check(pair<Hash, Hash> q, pair<long long, long long> len) {
  if (q.first == q.second && len.first == len.second) return false;
  Hash w = Hash(0, 0);
  for (long long i = 0; i < ss; i++) {
    if (s[i] == '1') {
      w = w * len.second + q.second;
    } else {
      w = w * len.first + q.first;
    }
  }
  if (get_h(0, ts - 1, v) == w) return true;
  return false;
}
void revers(string &s) {
  for (long long i = 0; i < ss; i++) {
    if (s[i] == '0')
      s[i] = '1';
    else
      s[i] = '0';
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  precalc();
  cin >> s >> t;
  ts = t.size();
  ss = s.size();
  if (s[0] == '1') {
    revers(s);
  }
  build(t, v);
  long long ke = 0, kn = 0;
  long long inde;
  for (long long i = 0; i < ss; i++) {
    if (s[i] == '1')
      ke++;
    else
      kn++;
  }
  for (long long i = 0; i < ss; i++) {
    if (s[i] == '1') {
      inde = i;
      break;
    }
  }
  long long ste;
  long long ans = 0;
  for (long long i = 1; i < ts; i++) {
    ste = i * inde;
    if (i * kn < ts && (ts - i * kn) % ke == 0 && ste % i == 0) {
      if (check(make_pair(get_h(0, i - 1, v),
                          get_h(ste, (ts - i * kn) / ke + ste - 1, v)),
                make_pair(i, (ts - i * kn) / ke))) {
        ans++;
      }
    }
  }
  cout << ans;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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 T>
bool uax(T &a, const T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool uin(T &a, const T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &p) {
  in >> p.first >> p.second;
  return in;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &out, pair<T1, T2> &p) {
  out << p.first << ' ' << p.second;
  return out;
}
const long long MOD1 = 1e9 + 7, MOD2 = 1e9 + 9, P1 = 29, P2 = 31;
const int N = 2000005;
long long val(char x) { return (x - 'a') + 1; }
vector<pair<long long, long long>> poww(N);
struct Hash {
  long long h1, h2;
  Hash() {}
  Hash(long long h1_, long long h2_) {
    h1 = h1_;
    h2 = h2_;
  }
  Hash operator*(long long ind) {
    return Hash((h1 * poww[ind].first) % MOD1, (h2 * poww[ind].second) % MOD2);
  }
  bool operator==(Hash q) { return (h1 == q.h1 && h2 == q.h2); }
  Hash operator-(Hash q) {
    return Hash((h1 - q.h1 + MOD1) % MOD1, (h2 - q.h2 + MOD2) % MOD2);
  }
  Hash operator+(Hash q) {
    return Hash((h1 + q.h1) % MOD1, (h2 + q.h2) % MOD2);
  }
};
long long n;
string s, t;
vector<Hash> v;
long long ts, ss;
void precalc() {
  poww[0] = make_pair(1, 1);
  for (long long i = 1; i < N; i++) {
    poww[i] = make_pair((poww[i - 1].first * P1) % MOD1,
                        (poww[i - 1].second * P2) % MOD2);
  }
}
void build(string &s, vector<Hash> &h) {
  h.assign(s.size(), Hash());
  h[0] = Hash(val(s[0]), val(s[0]));
  for (long long i = 1; i < s.size(); i++) {
    h[i] = Hash((h[i - 1].h1 * P1 + val(s[i])) % MOD1,
                (h[i - 1].h2 * P2 + val(s[i])) % MOD2);
  }
  return;
}
Hash get_h(long long l, long long r, vector<Hash> &h) {
  if (l) {
    return h[r] - h[l - 1] * (r - l + 1);
  }
  return h[r];
}
bool check(pair<Hash, Hash> q, pair<long long, long long> len) {
  if (q.first == q.second && len.first == len.second) return false;
  Hash w = Hash(0, 0);
  for (long long i = 0; i < ss; i++) {
    if (s[i] == '1') {
      w = w * len.second + q.second;
    } else {
      w = w * len.first + q.first;
    }
  }
  if (get_h(0, ts - 1, v) == w) return true;
  return false;
}
void revers(string &s) {
  for (long long i = 0; i < ss; i++) {
    if (s[i] == '0')
      s[i] = '1';
    else
      s[i] = '0';
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  precalc();
  cin >> s >> t;
  ts = t.size();
  ss = s.size();
  if (s[0] == '1') {
    revers(s);
  }
  build(t, v);
  long long ke = 0, kn = 0;
  long long inde;
  for (long long i = 0; i < ss; i++) {
    if (s[i] == '1')
      ke++;
    else
      kn++;
  }
  for (long long i = 0; i < ss; i++) {
    if (s[i] == '1') {
      inde = i;
      break;
    }
  }
  long long ste;
  long long ans = 0;
  for (long long i = 1; i < ts; i++) {
    ste = i * inde;
    if (i * kn < ts && (ts - i * kn) % ke == 0 && ste % i == 0) {
      if (check(make_pair(get_h(0, i - 1, v),
                          get_h(ste, (ts - i * kn) / ke + ste - 1, v)),
                make_pair(i, (ts - i * kn) / ke))) {
        ans++;
      }
    }
  }
  cout << ans;
}

```