#include <bits/stdc++.h>
using namespace std;
const int Mx = 2e6 + 9;
int lg[Mx];
char str[Mx];
int suf[Mx];
int rnk[Mx];
int tmprank[Mx];
int lcp[Mx];
struct cmp {
  int h;
  bool operator()(int i, int j) const {
    return rnk[i] < rnk[j] || (rnk[i] == rnk[j] && rnk[i + h] < rnk[j + h]);
  }
};
void buildSA() {
  int len = 0;
  do {
    suf[len] = len;
    rnk[len] = str[len];
  } while (str[len++]);
  for (int h = 1;; h <<= 1) {
    cmp c = {h};
    sort(suf, suf + len, c);
    for (int i = 1; i < len; i++) {
      tmprank[i] = tmprank[i - 1] + c(suf[i - 1], suf[i]);
    }
    for (int i = 0; i < len; i++) {
      rnk[suf[i]] = tmprank[i];
    }
    if (tmprank[len - 1] == len - 1) break;
  }
}
void build_lcp() {
  int len = 0;
  for (int i = 0; str[i]; i++) {
    int j = suf[rnk[i] - 1];
    while (str[i + len] == str[j + len]) len++;
    lcp[rnk[i]] = len;
    if (len) len--;
  }
}
string x, y;
int ST[20][Mx];
void buildST() {
  lg[0] = -1;
  for (int i = 1; i < Mx; ++i) {
    lg[i] = lg[i - 1] + !(i & (i - 1));
  }
  int n = y.size();
  for (int i = 0; i < 20; ++i) {
    for (int j = 1; j + (1 << i) <= n + 1; ++j) {
      if (i == 0)
        ST[i][j] = lcp[j];
      else
        ST[i][j] = min(ST[i - 1][j], ST[i - 1][j + (1 << (i - 1))]);
    }
  }
}
int getMin(int l, int r) {
  int len = r - l + 1;
  return min(ST[lg[len]][l], ST[lg[len]][r - (1 << lg[len]) + 1]);
}
int pos[Mx];
int check(int len, int rem) {
  int n = x.size();
  int a = -1, b = -1;
  for (int i = 0, j = 0; i < n; ++i) {
    if (x[i] == x[0]) {
      if (a == -1)
        a = pos[j];
      else {
        int l = a;
        int r = pos[j];
        if (r < l) swap(l, r);
        if (getMin(++l, r) < len) return 0;
      }
      j += len;
    } else {
      if (b == -1) {
        b = pos[j];
        if (len == rem) {
          int l = a;
          int r = b;
          if (r < l) swap(l, r);
          if (getMin(++l, r) >= len) return 0;
        }
      } else {
        int l = b;
        int r = pos[j];
        if (r < l) swap(l, r);
        if (getMin(++l, r) < rem) return 0;
      }
      j += rem;
    }
  }
  return 1;
}
int main() {
  cin >> x >> y;
  int a = 0, b = 0;
  for (int i = 0; i < x.size(); ++i) {
    a += x[i] == '0';
    b += x[i] == '1';
  }
  for (int i = 0; i < y.size(); ++i) str[i] = y[i];
  buildSA();
  build_lcp();
  buildST();
  for (int i = 1; i <= y.size(); ++i) {
    pos[suf[i]] = i;
  }
  int ans = 0;
  for (int i = 0; i < y.size() - 1; ++i) {
    int len = i + 1;
    bool flag = 1;
    long long tot = 1ll * len * max(a, b);
    if (tot >= y.size()) break;
    int rem = (int)y.size() - tot;
    if (rem % min(a, b)) continue;
    rem /= min(a, b);
    if (x[0] == '0' && max(a, b) == b) {
      swap(rem, len);
    } else if (x[0] == '1' && max(a, b) == a) {
      swap(rem, len);
    }
    ans += check(len, rem);
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Generate a Cpp solution 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;
const int Mx = 2e6 + 9;
int lg[Mx];
char str[Mx];
int suf[Mx];
int rnk[Mx];
int tmprank[Mx];
int lcp[Mx];
struct cmp {
  int h;
  bool operator()(int i, int j) const {
    return rnk[i] < rnk[j] || (rnk[i] == rnk[j] && rnk[i + h] < rnk[j + h]);
  }
};
void buildSA() {
  int len = 0;
  do {
    suf[len] = len;
    rnk[len] = str[len];
  } while (str[len++]);
  for (int h = 1;; h <<= 1) {
    cmp c = {h};
    sort(suf, suf + len, c);
    for (int i = 1; i < len; i++) {
      tmprank[i] = tmprank[i - 1] + c(suf[i - 1], suf[i]);
    }
    for (int i = 0; i < len; i++) {
      rnk[suf[i]] = tmprank[i];
    }
    if (tmprank[len - 1] == len - 1) break;
  }
}
void build_lcp() {
  int len = 0;
  for (int i = 0; str[i]; i++) {
    int j = suf[rnk[i] - 1];
    while (str[i + len] == str[j + len]) len++;
    lcp[rnk[i]] = len;
    if (len) len--;
  }
}
string x, y;
int ST[20][Mx];
void buildST() {
  lg[0] = -1;
  for (int i = 1; i < Mx; ++i) {
    lg[i] = lg[i - 1] + !(i & (i - 1));
  }
  int n = y.size();
  for (int i = 0; i < 20; ++i) {
    for (int j = 1; j + (1 << i) <= n + 1; ++j) {
      if (i == 0)
        ST[i][j] = lcp[j];
      else
        ST[i][j] = min(ST[i - 1][j], ST[i - 1][j + (1 << (i - 1))]);
    }
  }
}
int getMin(int l, int r) {
  int len = r - l + 1;
  return min(ST[lg[len]][l], ST[lg[len]][r - (1 << lg[len]) + 1]);
}
int pos[Mx];
int check(int len, int rem) {
  int n = x.size();
  int a = -1, b = -1;
  for (int i = 0, j = 0; i < n; ++i) {
    if (x[i] == x[0]) {
      if (a == -1)
        a = pos[j];
      else {
        int l = a;
        int r = pos[j];
        if (r < l) swap(l, r);
        if (getMin(++l, r) < len) return 0;
      }
      j += len;
    } else {
      if (b == -1) {
        b = pos[j];
        if (len == rem) {
          int l = a;
          int r = b;
          if (r < l) swap(l, r);
          if (getMin(++l, r) >= len) return 0;
        }
      } else {
        int l = b;
        int r = pos[j];
        if (r < l) swap(l, r);
        if (getMin(++l, r) < rem) return 0;
      }
      j += rem;
    }
  }
  return 1;
}
int main() {
  cin >> x >> y;
  int a = 0, b = 0;
  for (int i = 0; i < x.size(); ++i) {
    a += x[i] == '0';
    b += x[i] == '1';
  }
  for (int i = 0; i < y.size(); ++i) str[i] = y[i];
  buildSA();
  build_lcp();
  buildST();
  for (int i = 1; i <= y.size(); ++i) {
    pos[suf[i]] = i;
  }
  int ans = 0;
  for (int i = 0; i < y.size() - 1; ++i) {
    int len = i + 1;
    bool flag = 1;
    long long tot = 1ll * len * max(a, b);
    if (tot >= y.size()) break;
    int rem = (int)y.size() - tot;
    if (rem % min(a, b)) continue;
    rem /= min(a, b);
    if (x[0] == '0' && max(a, b) == b) {
      swap(rem, len);
    } else if (x[0] == '1' && max(a, b) == a) {
      swap(rem, len);
    }
    ans += check(len, rem);
  }
  cout << ans << endl;
  return 0;
}

```