#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void chkmax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
inline void chkmin(T &a, T b) {
  if (a > b) a = b;
}
inline int read() {
  int sum = 0, p = 1;
  char ch = getchar();
  while (!(('0' <= ch && ch <= '9') || ch == '-')) ch = getchar();
  if (ch == '-') p = -1, ch = getchar();
  while ('0' <= ch && ch <= '9') sum = sum * 10 + ch - 48, ch = getchar();
  return sum * p;
}
const int maxn = 1e6 + 20;
const int inf = 0x3f3f3f3f;
char S[maxn];
int n0, n1, n, m;
char T[maxn];
int tag[maxn], v[maxn], x[maxn], y[maxn], sa[maxn], rk[maxn], ht[maxn];
int st[maxn][20], lg[maxn];
inline void get_sa(int n) {
  int m = 26;
  for (int i = (1), _end_ = (n); i <= _end_; i++) tag[x[i] = T[i] - 'a' + 1]++;
  for (int i = (1), _end_ = (m); i <= _end_; i++) tag[i] += tag[i - 1];
  for (int i = (n), _end_ = (1); i >= _end_; i--) sa[tag[x[i]]--] = i;
  for (int j = 1, p = 0; p < n; m = p, j <<= 1) {
    p = 0;
    for (int i = (n - j + 1), _end_ = (n); i <= _end_; i++) y[++p] = i;
    for (int i = (1), _end_ = (n); i <= _end_; i++)
      if (sa[i] > j) y[++p] = sa[i] - j;
    for (int i = (1), _end_ = (m); i <= _end_; i++) tag[i] = 0;
    for (int i = (1), _end_ = (n); i <= _end_; i++) tag[v[i] = x[y[i]]]++;
    for (int i = (1), _end_ = (m); i <= _end_; i++) tag[i] += tag[i - 1];
    for (int i = (n), _end_ = (1); i >= _end_; i--) sa[tag[v[i]]--] = y[i];
    for (int i = (1), _end_ = (n); i <= _end_; i++) v[i] = x[i];
    p = 1;
    x[sa[1]] = 1;
    for (int i = (2), _end_ = (n); i <= _end_; i++)
      x[sa[i]] = v[sa[i]] == v[sa[i - 1]] && v[sa[i] + j] == v[sa[i - 1] + j]
                     ? p
                     : ++p;
  }
  for (int i = (1), _end_ = (n); i <= _end_; i++) rk[sa[i]] = i;
  int j = 0;
  for (int i = (1), _end_ = (n); i <= _end_; i++) {
    if (rk[i] == n) continue;
    if (j) j--;
    while (i + j <= n && sa[rk[i] + 1] + j <= n &&
           T[i + j] == T[sa[rk[i] + 1] + j])
      ++j;
    ht[rk[i]] = j;
  }
  for (int i = (1), _end_ = (n - 1); i <= _end_; i++) st[i][0] = ht[i];
  for (int j = 1; (1 << j) < n; j++)
    for (int i = (1), _end_ = ((n - (1 << j))); i <= _end_; i++)
      st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
  for (int i = (2), _end_ = (n - 1); i <= _end_; i++) lg[i] = lg[i >> 1] + 1;
}
inline int query(int l, int r) {
  if (l == r) return inf;
  int L = rk[l], R = rk[r];
  if (L > R) swap(L, R);
  R--;
  int k = lg[R - L + 1];
  return min(st[L][k], st[R - (1 << k) + 1][k]);
}
inline void debug() { cerr << query(1, 3) << endl; }
inline void init() {
  scanf("%s", S + 1);
  n = strlen(S + 1);
  scanf("%s", T + 1);
  m = strlen(T + 1);
  for (int i = (1), _end_ = (n); i <= _end_; i++)
    if (S[i] == '0')
      n0++;
    else
      n1++;
  get_sa(m);
}
inline void doing() {
  int ans = 0;
  for (int x = (1), _end_ = (m / n0); x <= _end_; x++)
    if (!((m - x * n0) % n1)) {
      int y = (m - x * n0) / n1;
      if (!y) continue;
      int now = 1, l0 = -1, l1 = -1, flg = 0;
      for (int i = (1), _end_ = (n); i <= _end_; i++) {
        if (S[i] == '0') {
          if (l0 == -1)
            l0 = now;
          else if (query(now, l0) < x) {
            flg = 1;
            break;
          }
          now += x;
        } else {
          if (l1 == -1)
            l1 = now;
          else if (query(now, l1) < y) {
            flg = 1;
            break;
          }
          now += y;
        }
      }
      ans += !flg && (x != y || query(l0, l1) < x);
    }
  printf("%d\n", ans);
}
int main() {
  init();
  doing();
  return 0;
}

### Prompt

Your challenge is to write 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;
template <class T>
inline void chkmax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
inline void chkmin(T &a, T b) {
  if (a > b) a = b;
}
inline int read() {
  int sum = 0, p = 1;
  char ch = getchar();
  while (!(('0' <= ch && ch <= '9') || ch == '-')) ch = getchar();
  if (ch == '-') p = -1, ch = getchar();
  while ('0' <= ch && ch <= '9') sum = sum * 10 + ch - 48, ch = getchar();
  return sum * p;
}
const int maxn = 1e6 + 20;
const int inf = 0x3f3f3f3f;
char S[maxn];
int n0, n1, n, m;
char T[maxn];
int tag[maxn], v[maxn], x[maxn], y[maxn], sa[maxn], rk[maxn], ht[maxn];
int st[maxn][20], lg[maxn];
inline void get_sa(int n) {
  int m = 26;
  for (int i = (1), _end_ = (n); i <= _end_; i++) tag[x[i] = T[i] - 'a' + 1]++;
  for (int i = (1), _end_ = (m); i <= _end_; i++) tag[i] += tag[i - 1];
  for (int i = (n), _end_ = (1); i >= _end_; i--) sa[tag[x[i]]--] = i;
  for (int j = 1, p = 0; p < n; m = p, j <<= 1) {
    p = 0;
    for (int i = (n - j + 1), _end_ = (n); i <= _end_; i++) y[++p] = i;
    for (int i = (1), _end_ = (n); i <= _end_; i++)
      if (sa[i] > j) y[++p] = sa[i] - j;
    for (int i = (1), _end_ = (m); i <= _end_; i++) tag[i] = 0;
    for (int i = (1), _end_ = (n); i <= _end_; i++) tag[v[i] = x[y[i]]]++;
    for (int i = (1), _end_ = (m); i <= _end_; i++) tag[i] += tag[i - 1];
    for (int i = (n), _end_ = (1); i >= _end_; i--) sa[tag[v[i]]--] = y[i];
    for (int i = (1), _end_ = (n); i <= _end_; i++) v[i] = x[i];
    p = 1;
    x[sa[1]] = 1;
    for (int i = (2), _end_ = (n); i <= _end_; i++)
      x[sa[i]] = v[sa[i]] == v[sa[i - 1]] && v[sa[i] + j] == v[sa[i - 1] + j]
                     ? p
                     : ++p;
  }
  for (int i = (1), _end_ = (n); i <= _end_; i++) rk[sa[i]] = i;
  int j = 0;
  for (int i = (1), _end_ = (n); i <= _end_; i++) {
    if (rk[i] == n) continue;
    if (j) j--;
    while (i + j <= n && sa[rk[i] + 1] + j <= n &&
           T[i + j] == T[sa[rk[i] + 1] + j])
      ++j;
    ht[rk[i]] = j;
  }
  for (int i = (1), _end_ = (n - 1); i <= _end_; i++) st[i][0] = ht[i];
  for (int j = 1; (1 << j) < n; j++)
    for (int i = (1), _end_ = ((n - (1 << j))); i <= _end_; i++)
      st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
  for (int i = (2), _end_ = (n - 1); i <= _end_; i++) lg[i] = lg[i >> 1] + 1;
}
inline int query(int l, int r) {
  if (l == r) return inf;
  int L = rk[l], R = rk[r];
  if (L > R) swap(L, R);
  R--;
  int k = lg[R - L + 1];
  return min(st[L][k], st[R - (1 << k) + 1][k]);
}
inline void debug() { cerr << query(1, 3) << endl; }
inline void init() {
  scanf("%s", S + 1);
  n = strlen(S + 1);
  scanf("%s", T + 1);
  m = strlen(T + 1);
  for (int i = (1), _end_ = (n); i <= _end_; i++)
    if (S[i] == '0')
      n0++;
    else
      n1++;
  get_sa(m);
}
inline void doing() {
  int ans = 0;
  for (int x = (1), _end_ = (m / n0); x <= _end_; x++)
    if (!((m - x * n0) % n1)) {
      int y = (m - x * n0) / n1;
      if (!y) continue;
      int now = 1, l0 = -1, l1 = -1, flg = 0;
      for (int i = (1), _end_ = (n); i <= _end_; i++) {
        if (S[i] == '0') {
          if (l0 == -1)
            l0 = now;
          else if (query(now, l0) < x) {
            flg = 1;
            break;
          }
          now += x;
        } else {
          if (l1 == -1)
            l1 = now;
          else if (query(now, l1) < y) {
            flg = 1;
            break;
          }
          now += y;
        }
      }
      ans += !flg && (x != y || query(l0, l1) < x);
    }
  printf("%d\n", ans);
}
int main() {
  init();
  doing();
  return 0;
}

```