#include <bits/stdc++.h>
using namespace std;
uint64_t rnd_data = 0xDEADBEEFDULL;
inline void my_srand(int seed) { rnd_data = ((uint64_t)seed << 16) | 0x330E; }
inline int my_rand() {
  rnd_data = rnd_data * 0x5DEECE66DULL + 0xB;
  return (rnd_data >> 17) & 0x7FFFFFFF;
}
template <typename T>
void my_random_shuffle(T b, T e) {
  for (int i = (1); i <= (int)((int)(e - b) - 1); i++) {
    swap(b[i], b[my_rand() % (i + 1)]);
  }
}
template <class _T>
inline _T sqr(const _T &x) {
  return x * x;
}
template <typename type_t, typename less_t = std::less<type_t>>
inline bool uin(type_t &a, const type_t &b, const less_t &ls = less_t()) {
  return ls(b, a) ? a = b, true : false;
}
template <typename type_t, typename less_t = std::less<type_t>>
inline bool uax(type_t &a, const type_t &b, const less_t &ls = less_t()) {
  return ls(a, b) ? a = b, true : false;
}
const long double PI = 3.1415926535897932384626433832795L;
const long double EPS = 1e-9;
const int HS = 2;
int p[HS];
int b[HS];
int push_back[1024000][HS];
struct th {
  int h[HS];
  bool operator==(const th &r) const {
    for (int i = 0; i < (int)(HS); i++) {
      if (h[i] != r.h[i]) return false;
    }
    return true;
  }
  bool operator!=(const th &r) const { return !(operator==(r)); }
};
th operator-(const th &l, const th &r) {
  th res;
  for (int i = 0; i < (int)(HS); i++) {
    res.h[i] = l.h[i] - r.h[i];
    if (res.h[i] < 0) res.h[i] += p[i];
    assert(res.h[i] >= 0);
  }
  return res;
}
th operator*(const th &l, int k) {
  th res = l;
  for (int i = 0; i < (int)(HS); i++) {
    assert(res.h[i] >= 0);
    res.h[i] = res.h[i] * (long long)push_back[k][i] % p[i];
  }
  return res;
}
int n;
char s[102400];
char t[1024000];
th h[1024000];
int sl, tl;
th calc_h(int l, int len) { return (h[l + len] - h[l]) * (tl - l); }
int pr[] = {100020191, 100020149, 100020121, 100020131, 100020133,
            100020103, 100020023, 100120183, 100120159, 100120091,
            100120067, 100120037, 100120003};
int ps = sizeof(pr) / sizeof(pr[0]);
int main() {
  long long z = chrono::system_clock::now().time_since_epoch().count();
  my_srand(z);
  p[0] = pr[my_rand() % ps];
  do {
    p[1] = pr[my_rand() % ps];
  } while (p[0] == p[1]);
  b[0] = 239;
  b[1] = 311;
  int c[2] = {};
  scanf("%s", s);
  scanf("%s", t);
  sl = strlen(s);
  tl = strlen(t);
  for (int i = 0; i < (int)(HS); i++) {
    push_back[0][i] = 1;
  }
  for (int i = 0; i < (int)(tl + 2); i++) {
    for (int j = 0; j < (int)(HS); j++) {
      push_back[i + 1][j] = push_back[i][j] * (long long)b[j] % p[j];
    }
  }
  memset((h), 0, sizeof(h));
  for (int i = 0; i < (int)(tl); i++) {
    h[i + 1] = h[i];
    for (int j = 0; j < (int)(HS); j++) {
      h[i + 1].h[j] =
          (h[i + 1].h[j] + push_back[i][j] * (long long)t[i]) % p[j];
    }
  }
  int f[2] = {-1, -1};
  for (int i = 0; i < (int)(sl); i++) {
    int z = s[i] - '0';
    ++c[z];
    if (f[z] < 0) f[z] = i;
  }
  char c0 = s[0];
  int ans = 0;
  for (int l = (1); l <= (int)(tl); l++) {
    long long ll = l * (long long)c[c0 - '0'];
    int z = (c0 - '0') ^ 1;
    if (ll >= tl) continue;
    int rem = tl - ll;
    if (rem % c[z]) continue;
    int l0 = l;
    int l1 = rem / c[z];
    if (c0 == '1') swap(l0, l1);
    int st0 = 0, st1 = 0;
    if (f[0])
      st0 = l1 * f[0];
    else
      st1 = l0 * f[1];
    th h0 = calc_h(st0, l0);
    th h1 = calc_h(st1, l1);
    if (h0 == h1) continue;
    int pos = 0;
    bool ok = true;
    for (int i = 0; i < (int)(sl); i++) {
      if (s[i] == '0') {
        th curh = calc_h(pos, l0);
        if (curh != h0) {
          ok = false;
          break;
        }
        pos += l0;
      } else {
        th curh = calc_h(pos, l1);
        if (curh != h1) {
          ok = false;
          break;
        }
        pos += l1;
      }
      if (!ok) break;
    }
    if (ok) {
      ans++;
    }
  }
  printf("%d\n", ans);
  return 0;
}

### Prompt

Develop a solution in CPP 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;
uint64_t rnd_data = 0xDEADBEEFDULL;
inline void my_srand(int seed) { rnd_data = ((uint64_t)seed << 16) | 0x330E; }
inline int my_rand() {
  rnd_data = rnd_data * 0x5DEECE66DULL + 0xB;
  return (rnd_data >> 17) & 0x7FFFFFFF;
}
template <typename T>
void my_random_shuffle(T b, T e) {
  for (int i = (1); i <= (int)((int)(e - b) - 1); i++) {
    swap(b[i], b[my_rand() % (i + 1)]);
  }
}
template <class _T>
inline _T sqr(const _T &x) {
  return x * x;
}
template <typename type_t, typename less_t = std::less<type_t>>
inline bool uin(type_t &a, const type_t &b, const less_t &ls = less_t()) {
  return ls(b, a) ? a = b, true : false;
}
template <typename type_t, typename less_t = std::less<type_t>>
inline bool uax(type_t &a, const type_t &b, const less_t &ls = less_t()) {
  return ls(a, b) ? a = b, true : false;
}
const long double PI = 3.1415926535897932384626433832795L;
const long double EPS = 1e-9;
const int HS = 2;
int p[HS];
int b[HS];
int push_back[1024000][HS];
struct th {
  int h[HS];
  bool operator==(const th &r) const {
    for (int i = 0; i < (int)(HS); i++) {
      if (h[i] != r.h[i]) return false;
    }
    return true;
  }
  bool operator!=(const th &r) const { return !(operator==(r)); }
};
th operator-(const th &l, const th &r) {
  th res;
  for (int i = 0; i < (int)(HS); i++) {
    res.h[i] = l.h[i] - r.h[i];
    if (res.h[i] < 0) res.h[i] += p[i];
    assert(res.h[i] >= 0);
  }
  return res;
}
th operator*(const th &l, int k) {
  th res = l;
  for (int i = 0; i < (int)(HS); i++) {
    assert(res.h[i] >= 0);
    res.h[i] = res.h[i] * (long long)push_back[k][i] % p[i];
  }
  return res;
}
int n;
char s[102400];
char t[1024000];
th h[1024000];
int sl, tl;
th calc_h(int l, int len) { return (h[l + len] - h[l]) * (tl - l); }
int pr[] = {100020191, 100020149, 100020121, 100020131, 100020133,
            100020103, 100020023, 100120183, 100120159, 100120091,
            100120067, 100120037, 100120003};
int ps = sizeof(pr) / sizeof(pr[0]);
int main() {
  long long z = chrono::system_clock::now().time_since_epoch().count();
  my_srand(z);
  p[0] = pr[my_rand() % ps];
  do {
    p[1] = pr[my_rand() % ps];
  } while (p[0] == p[1]);
  b[0] = 239;
  b[1] = 311;
  int c[2] = {};
  scanf("%s", s);
  scanf("%s", t);
  sl = strlen(s);
  tl = strlen(t);
  for (int i = 0; i < (int)(HS); i++) {
    push_back[0][i] = 1;
  }
  for (int i = 0; i < (int)(tl + 2); i++) {
    for (int j = 0; j < (int)(HS); j++) {
      push_back[i + 1][j] = push_back[i][j] * (long long)b[j] % p[j];
    }
  }
  memset((h), 0, sizeof(h));
  for (int i = 0; i < (int)(tl); i++) {
    h[i + 1] = h[i];
    for (int j = 0; j < (int)(HS); j++) {
      h[i + 1].h[j] =
          (h[i + 1].h[j] + push_back[i][j] * (long long)t[i]) % p[j];
    }
  }
  int f[2] = {-1, -1};
  for (int i = 0; i < (int)(sl); i++) {
    int z = s[i] - '0';
    ++c[z];
    if (f[z] < 0) f[z] = i;
  }
  char c0 = s[0];
  int ans = 0;
  for (int l = (1); l <= (int)(tl); l++) {
    long long ll = l * (long long)c[c0 - '0'];
    int z = (c0 - '0') ^ 1;
    if (ll >= tl) continue;
    int rem = tl - ll;
    if (rem % c[z]) continue;
    int l0 = l;
    int l1 = rem / c[z];
    if (c0 == '1') swap(l0, l1);
    int st0 = 0, st1 = 0;
    if (f[0])
      st0 = l1 * f[0];
    else
      st1 = l0 * f[1];
    th h0 = calc_h(st0, l0);
    th h1 = calc_h(st1, l1);
    if (h0 == h1) continue;
    int pos = 0;
    bool ok = true;
    for (int i = 0; i < (int)(sl); i++) {
      if (s[i] == '0') {
        th curh = calc_h(pos, l0);
        if (curh != h0) {
          ok = false;
          break;
        }
        pos += l0;
      } else {
        th curh = calc_h(pos, l1);
        if (curh != h1) {
          ok = false;
          break;
        }
        pos += l1;
      }
      if (!ok) break;
    }
    if (ok) {
      ans++;
    }
  }
  printf("%d\n", ans);
  return 0;
}

```