#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
char c[maxn], s[maxn];
unsigned long long p[2] = {13331, 13332};
unsigned long long hs[maxn][2], f[maxn][2];
int n, m;
unsigned long long get(int l, int r) {
  return hs[r][0] - hs[l - 1][0] * f[r - l + 1][0];
}
unsigned long long get2(int l, int r) {
  return hs[r][1] - hs[l - 1][1] * f[r - l + 1][1];
}
bool check(int x, int y) {
  unsigned long long r = 0, r2 = 0;
  unsigned long long rr = 0, rr2 = 0;
  int id = 1;
  for (int i = 1; i <= m; i++) {
    if (c[i] == '0') {
      if (r == 0)
        r = get(id, id + x - 1), rr = get2(id, id + x - 1);
      else if (get(id, id + x - 1) != r || get2(id, id + x - 1) != rr)
        return false;
      id += x;
    } else {
      if (r2 == 0)
        r2 = get(id, id + y - 1), rr2 = get2(id, id + y - 1);
      else if (get(id, id + y - 1) != r2 || get2(id, id + y - 1) != rr2)
        return false;
      id += y;
    }
  }
  if (x == y) {
    string sss = "", ssss = "";
    for (int i = 1; i <= m; i++) {
      if (c[i] == '0') {
        for (int j = 1 + x * (i - 1); j < 1 + x * i; j++) sss += s[j];
        break;
      }
    }
    for (int i = 1; i <= m; i++) {
      if (c[i] == '1') {
        for (int j = 1 + y * (i - 1); j < 1 + y * i; j++) ssss += s[j];
        break;
      }
    }
    return sss != ssss;
  }
  return true;
}
int main() {
  scanf("%s", c + 1);
  scanf("%s", s + 1);
  f[0][0] = f[0][1] = 1;
  n = strlen(s + 1);
  for (int i = 1; i <= n; i++) {
    hs[i][0] = hs[i - 1][0] * p[0] + s[i];
    f[i][0] = f[i - 1][0] * p[0];
    hs[i][1] = hs[i - 1][1] * p[1] + s[i];
    f[i][1] = f[i - 1][1] * p[1];
  }
  m = strlen(c + 1);
  int a = 0, b = 0;
  for (int i = 1; i <= m; i++) {
    if (c[i] == '0')
      a++;
    else
      b++;
  }
  int ans = 0;
  for (int x = 1;; x++) {
    if (a * x >= n) break;
    if ((n - a * x) % b == 0) {
      int y = (n - a * x) / b;
      if (check(x, y)) ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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;
const int maxn = 1e6 + 5;
char c[maxn], s[maxn];
unsigned long long p[2] = {13331, 13332};
unsigned long long hs[maxn][2], f[maxn][2];
int n, m;
unsigned long long get(int l, int r) {
  return hs[r][0] - hs[l - 1][0] * f[r - l + 1][0];
}
unsigned long long get2(int l, int r) {
  return hs[r][1] - hs[l - 1][1] * f[r - l + 1][1];
}
bool check(int x, int y) {
  unsigned long long r = 0, r2 = 0;
  unsigned long long rr = 0, rr2 = 0;
  int id = 1;
  for (int i = 1; i <= m; i++) {
    if (c[i] == '0') {
      if (r == 0)
        r = get(id, id + x - 1), rr = get2(id, id + x - 1);
      else if (get(id, id + x - 1) != r || get2(id, id + x - 1) != rr)
        return false;
      id += x;
    } else {
      if (r2 == 0)
        r2 = get(id, id + y - 1), rr2 = get2(id, id + y - 1);
      else if (get(id, id + y - 1) != r2 || get2(id, id + y - 1) != rr2)
        return false;
      id += y;
    }
  }
  if (x == y) {
    string sss = "", ssss = "";
    for (int i = 1; i <= m; i++) {
      if (c[i] == '0') {
        for (int j = 1 + x * (i - 1); j < 1 + x * i; j++) sss += s[j];
        break;
      }
    }
    for (int i = 1; i <= m; i++) {
      if (c[i] == '1') {
        for (int j = 1 + y * (i - 1); j < 1 + y * i; j++) ssss += s[j];
        break;
      }
    }
    return sss != ssss;
  }
  return true;
}
int main() {
  scanf("%s", c + 1);
  scanf("%s", s + 1);
  f[0][0] = f[0][1] = 1;
  n = strlen(s + 1);
  for (int i = 1; i <= n; i++) {
    hs[i][0] = hs[i - 1][0] * p[0] + s[i];
    f[i][0] = f[i - 1][0] * p[0];
    hs[i][1] = hs[i - 1][1] * p[1] + s[i];
    f[i][1] = f[i - 1][1] * p[1];
  }
  m = strlen(c + 1);
  int a = 0, b = 0;
  for (int i = 1; i <= m; i++) {
    if (c[i] == '0')
      a++;
    else
      b++;
  }
  int ans = 0;
  for (int x = 1;; x++) {
    if (a * x >= n) break;
    if ((n - a * x) % b == 0) {
      int y = (n - a * x) / b;
      if (check(x, y)) ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

```