#include <bits/stdc++.h>
using namespace ::std;
const long double PI = acos(-1);
const long long MOD = 1000000000 + 7;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long add(long long a, long long b, long long m = MOD) {
  return (a % m + b % m + 2 * m) % m;
}
long long mul(long long a, long long b, long long m = MOD) {
  return ((a % m + m) * (b % m + m)) % m;
}
long long pow_mod(long long a, long long b, long long m = MOD) {
  long long res = 1LL;
  a = a % m;
  while (b) {
    if (b & 1) res = mul(res, a, m);
    b >>= 1;
    a = mul(a, a, m);
  }
  return res;
}
long long fastexp(long long a, long long b) {
  long long res = 1LL;
  while (b) {
    if (b & 1) res = res * a;
    b >>= 1;
    a *= a;
  }
  return res;
}
int gcdExtendido(int a, int b, int *x, int *y) {
  if (a == 0) {
    *x = 0;
    *y = 1;
    return b;
  }
  int x1, y1;
  int gcd = gcdExtendido(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return gcd;
}
int modInverso(int a, int m) {
  int x, y;
  int g = gcdExtendido(a, m, &x, &y);
  if (g != 1)
    return -1;
  else
    return (x % m + m) % m;
}
const int N = 1000000 + 5;
const int M = 1000000000 + 9999;
const int B = 257;
int n, m;
int pi[N];
int ac[N];
char s[N];
char t[N];
int q0, q1;
int getH(int L, int R) {
  if (L == 0) return ac[R];
  return mul(add(ac[R], mul(ac[L - 1], M - 1, M), M), pi[L], M);
}
bool can(int L0, int L1) {
  int hash0 = -1;
  int hash1 = -1;
  int p = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == '0') {
      if (hash0 == -1) {
        hash0 = getH(p, p + L0 - 1);
      } else {
        if (hash0 != getH(p, p + L0 - 1)) return false;
      }
      p += L0;
    } else {
      if (hash1 == -1) {
        hash1 = getH(p, p + L1 - 1);
      } else {
        if (hash1 != getH(p, p + L1 - 1)) return false;
      }
      p += L1;
    }
    if (hash0 != -1 and hash1 != -1 and hash0 == hash1 and L0 == L1)
      return false;
  }
  return true;
}
int main() {
  scanf("%s", s);
  scanf("%s", t);
  n = strlen(s);
  m = strlen(t);
  pi[1] = pow_mod(B, M - 2, M);
  pi[0] = 1;
  for (int i = 2; i < m; i++) {
    pi[i] = mul(pi[i - 1], pi[1], M);
  }
  int p = 1;
  ac[0] = add(t[0] - 'a', 0, M);
  p = mul(p, B, M);
  for (int i = 1; i < m; i++) {
    ac[i] = add(ac[i - 1], mul(p, t[i] - 'a', M), M);
    p = mul(p, B, M);
  }
  for (int i = 0; i < n; i++) {
    if (s[i] == '0')
      q0++;
    else
      q1++;
  }
  int ans = 0;
  for (int L = 1; L * q0 <= m; L++) {
    int rest = m - L * q0;
    if (rest <= 0) continue;
    if (rest % q1) continue;
    int L2 = rest / q1;
    if (can(L, L2)) {
      ans++;
    }
  }
  printf("%d\n", ans);
  return 0;
}

### Prompt

Please provide a cpp coded solution 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;
const long double PI = acos(-1);
const long long MOD = 1000000000 + 7;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long add(long long a, long long b, long long m = MOD) {
  return (a % m + b % m + 2 * m) % m;
}
long long mul(long long a, long long b, long long m = MOD) {
  return ((a % m + m) * (b % m + m)) % m;
}
long long pow_mod(long long a, long long b, long long m = MOD) {
  long long res = 1LL;
  a = a % m;
  while (b) {
    if (b & 1) res = mul(res, a, m);
    b >>= 1;
    a = mul(a, a, m);
  }
  return res;
}
long long fastexp(long long a, long long b) {
  long long res = 1LL;
  while (b) {
    if (b & 1) res = res * a;
    b >>= 1;
    a *= a;
  }
  return res;
}
int gcdExtendido(int a, int b, int *x, int *y) {
  if (a == 0) {
    *x = 0;
    *y = 1;
    return b;
  }
  int x1, y1;
  int gcd = gcdExtendido(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return gcd;
}
int modInverso(int a, int m) {
  int x, y;
  int g = gcdExtendido(a, m, &x, &y);
  if (g != 1)
    return -1;
  else
    return (x % m + m) % m;
}
const int N = 1000000 + 5;
const int M = 1000000000 + 9999;
const int B = 257;
int n, m;
int pi[N];
int ac[N];
char s[N];
char t[N];
int q0, q1;
int getH(int L, int R) {
  if (L == 0) return ac[R];
  return mul(add(ac[R], mul(ac[L - 1], M - 1, M), M), pi[L], M);
}
bool can(int L0, int L1) {
  int hash0 = -1;
  int hash1 = -1;
  int p = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == '0') {
      if (hash0 == -1) {
        hash0 = getH(p, p + L0 - 1);
      } else {
        if (hash0 != getH(p, p + L0 - 1)) return false;
      }
      p += L0;
    } else {
      if (hash1 == -1) {
        hash1 = getH(p, p + L1 - 1);
      } else {
        if (hash1 != getH(p, p + L1 - 1)) return false;
      }
      p += L1;
    }
    if (hash0 != -1 and hash1 != -1 and hash0 == hash1 and L0 == L1)
      return false;
  }
  return true;
}
int main() {
  scanf("%s", s);
  scanf("%s", t);
  n = strlen(s);
  m = strlen(t);
  pi[1] = pow_mod(B, M - 2, M);
  pi[0] = 1;
  for (int i = 2; i < m; i++) {
    pi[i] = mul(pi[i - 1], pi[1], M);
  }
  int p = 1;
  ac[0] = add(t[0] - 'a', 0, M);
  p = mul(p, B, M);
  for (int i = 1; i < m; i++) {
    ac[i] = add(ac[i - 1], mul(p, t[i] - 'a', M), M);
    p = mul(p, B, M);
  }
  for (int i = 0; i < n; i++) {
    if (s[i] == '0')
      q0++;
    else
      q1++;
  }
  int ans = 0;
  for (int L = 1; L * q0 <= m; L++) {
    int rest = m - L * q0;
    if (rest <= 0) continue;
    if (rest % q1) continue;
    int L2 = rest / q1;
    if (can(L, L2)) {
      ans++;
    }
  }
  printf("%d\n", ans);
  return 0;
}

```