#include <bits/stdc++.h>
int read() {
  int x = 0, f = 1;
  char c;
  do {
    c = getchar();
    if (c == '-') f = -1;
  } while (c < '0' || c > '9');
  do {
    x = x * 10 + c - '0';
    c = getchar();
  } while (c >= '0' && c <= '9');
  return f * x;
}
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
bool umin(int &a, int b) {
  if (b < a) return a = b, 1;
  return 0;
}
bool umax(int &a, int b) {
  if (b > a) return a = b, 1;
  return 0;
}
int sa[1000001], rk[1000001], tp[1000001], c[1000001];
char s[1000001], t[1000001];
void radix_sort(int n, int m) {
  for (int i = 1; i <= m; ++i) c[i] = 0;
  for (int i = 1; i <= n; ++i) ++c[rk[i]];
  for (int i = 1; i <= m; ++i) c[i] += c[i - 1];
  for (int i = n; i; --i) sa[c[rk[tp[i]]]--] = tp[i];
}
void make_SA(int n, int m = 128) {
  for (int i = 1; i <= n; ++i) rk[i] = s[i], tp[i] = i;
  radix_sort(n, m);
  for (int k = 1; k <= n; k <<= 1) {
    int cur = 0;
    for (int i = n - k + 1; i <= n; ++i) tp[++cur] = i;
    for (int i = 1; i <= n; ++i)
      if (sa[i] > k) tp[++cur] = sa[i] - k;
    radix_sort(n, m);
    std::swap(rk, tp);
    cur = 1, rk[sa[1]] = 1;
    for (int i = 2; i <= n; ++i) {
      if (tp[sa[i]] != tp[sa[i - 1]] || tp[sa[i] + k] != tp[sa[i - 1] + k])
        ++cur;
      rk[sa[i]] = cur;
    }
    if (cur >= n) break;
    m = cur;
  }
}
int height[1000001];
void make_height(int n) {
  int k = 0;
  for (int i = 1; i <= n; ++i) {
    if (k > 0) --k;
    int j = sa[rk[i] - 1];
    while (s[i + k] == s[j + k]) ++k;
    height[rk[i]] = k;
  }
}
struct ST {
  int t[21][1000001], lg[1000001];
  void build(int *arr, int n) {
    lg[1] = 0;
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; ++i) t[0][i] = arr[i];
    for (int i = 1; i <= lg[n]; ++i)
      for (int j = 1; j + (1 << i) - 1 <= n; ++j)
        t[i][j] = min(t[i - 1][j], t[i - 1][j + (1 << (i - 1))]);
  }
  int Qmin(int l, int r) {
    if (l > r) std::swap(l, r);
    ++l;
    int k = lg[r - l];
    return min(t[k][l], t[k][r - (1 << k) + 1]);
  }
} st;
int main() {
  scanf("%s%s", t + 1, s + 1);
  int lent = strlen(t + 1), lens = strlen(s + 1), cnt0 = 0;
  make_SA(lens), make_height(lens);
  st.build(height, lens);
  for (int i = 1; i <= lent; ++i) cnt0 += (t[i] == '0');
  int ans = 0;
  if (cnt0 == lent) {
    if (lens % cnt0 == 0) {
      int i = lens / cnt0, pos = i + 1, flag = 1;
      for (int j = 2; j <= lent; pos += i, ++j)
        if (st.Qmin(rk[1], rk[pos]) < i) flag = 0;
      if (flag) ++ans;
    }
    printf("%d", ans);
    return 0;
  } else if (cnt0 == 0) {
    if (lens % (lent - cnt0) == 0) {
      int i = lens / (lent - cnt0), pos = i + 1, flag = 1;
      for (int j = 2; j <= lent; pos += i, ++j)
        if (st.Qmin(rk[1], rk[pos]) < i) flag = 0;
      if (flag) ++ans;
    }
    printf("%d", ans);
    return 0;
  }
  for (int i = 1; i * cnt0 <= lens; ++i) {
    if ((lens - i * cnt0) % (lent - cnt0)) continue;
    int start0 = 0, start1 = 0, pos = 1, flag = 1;
    int k = (lens - i * cnt0) / (lent - cnt0);
    for (int j = 1; j <= lent; ++j) {
      if (t[j] == '0') {
        if (!start0)
          start0 = pos;
        else if (st.Qmin(rk[start0], rk[pos]) < i)
          flag = 0;
        pos += i;
      } else {
        if (!start1)
          start1 = pos;
        else if (st.Qmin(rk[start1], rk[pos]) < k)
          flag = 0;
        if (!k) flag = 0;
        pos += k;
      }
    }
    if (flag && (i != k || st.Qmin(rk[start0], rk[start1]) < i)) ++ans;
  }
  printf("%d", 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>
int read() {
  int x = 0, f = 1;
  char c;
  do {
    c = getchar();
    if (c == '-') f = -1;
  } while (c < '0' || c > '9');
  do {
    x = x * 10 + c - '0';
    c = getchar();
  } while (c >= '0' && c <= '9');
  return f * x;
}
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
bool umin(int &a, int b) {
  if (b < a) return a = b, 1;
  return 0;
}
bool umax(int &a, int b) {
  if (b > a) return a = b, 1;
  return 0;
}
int sa[1000001], rk[1000001], tp[1000001], c[1000001];
char s[1000001], t[1000001];
void radix_sort(int n, int m) {
  for (int i = 1; i <= m; ++i) c[i] = 0;
  for (int i = 1; i <= n; ++i) ++c[rk[i]];
  for (int i = 1; i <= m; ++i) c[i] += c[i - 1];
  for (int i = n; i; --i) sa[c[rk[tp[i]]]--] = tp[i];
}
void make_SA(int n, int m = 128) {
  for (int i = 1; i <= n; ++i) rk[i] = s[i], tp[i] = i;
  radix_sort(n, m);
  for (int k = 1; k <= n; k <<= 1) {
    int cur = 0;
    for (int i = n - k + 1; i <= n; ++i) tp[++cur] = i;
    for (int i = 1; i <= n; ++i)
      if (sa[i] > k) tp[++cur] = sa[i] - k;
    radix_sort(n, m);
    std::swap(rk, tp);
    cur = 1, rk[sa[1]] = 1;
    for (int i = 2; i <= n; ++i) {
      if (tp[sa[i]] != tp[sa[i - 1]] || tp[sa[i] + k] != tp[sa[i - 1] + k])
        ++cur;
      rk[sa[i]] = cur;
    }
    if (cur >= n) break;
    m = cur;
  }
}
int height[1000001];
void make_height(int n) {
  int k = 0;
  for (int i = 1; i <= n; ++i) {
    if (k > 0) --k;
    int j = sa[rk[i] - 1];
    while (s[i + k] == s[j + k]) ++k;
    height[rk[i]] = k;
  }
}
struct ST {
  int t[21][1000001], lg[1000001];
  void build(int *arr, int n) {
    lg[1] = 0;
    for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; ++i) t[0][i] = arr[i];
    for (int i = 1; i <= lg[n]; ++i)
      for (int j = 1; j + (1 << i) - 1 <= n; ++j)
        t[i][j] = min(t[i - 1][j], t[i - 1][j + (1 << (i - 1))]);
  }
  int Qmin(int l, int r) {
    if (l > r) std::swap(l, r);
    ++l;
    int k = lg[r - l];
    return min(t[k][l], t[k][r - (1 << k) + 1]);
  }
} st;
int main() {
  scanf("%s%s", t + 1, s + 1);
  int lent = strlen(t + 1), lens = strlen(s + 1), cnt0 = 0;
  make_SA(lens), make_height(lens);
  st.build(height, lens);
  for (int i = 1; i <= lent; ++i) cnt0 += (t[i] == '0');
  int ans = 0;
  if (cnt0 == lent) {
    if (lens % cnt0 == 0) {
      int i = lens / cnt0, pos = i + 1, flag = 1;
      for (int j = 2; j <= lent; pos += i, ++j)
        if (st.Qmin(rk[1], rk[pos]) < i) flag = 0;
      if (flag) ++ans;
    }
    printf("%d", ans);
    return 0;
  } else if (cnt0 == 0) {
    if (lens % (lent - cnt0) == 0) {
      int i = lens / (lent - cnt0), pos = i + 1, flag = 1;
      for (int j = 2; j <= lent; pos += i, ++j)
        if (st.Qmin(rk[1], rk[pos]) < i) flag = 0;
      if (flag) ++ans;
    }
    printf("%d", ans);
    return 0;
  }
  for (int i = 1; i * cnt0 <= lens; ++i) {
    if ((lens - i * cnt0) % (lent - cnt0)) continue;
    int start0 = 0, start1 = 0, pos = 1, flag = 1;
    int k = (lens - i * cnt0) / (lent - cnt0);
    for (int j = 1; j <= lent; ++j) {
      if (t[j] == '0') {
        if (!start0)
          start0 = pos;
        else if (st.Qmin(rk[start0], rk[pos]) < i)
          flag = 0;
        pos += i;
      } else {
        if (!start1)
          start1 = pos;
        else if (st.Qmin(rk[start1], rk[pos]) < k)
          flag = 0;
        if (!k) flag = 0;
        pos += k;
      }
    }
    if (flag && (i != k || st.Qmin(rk[start0], rk[start1]) < i)) ++ans;
  }
  printf("%d", ans);
  return 0;
}

```