#include <bits/stdc++.h>
using namespace std;
string s, t;
long long int c0, c1;
long long int n, m;
long long int h[1000006];
long long int hh[1000005];
long long int p[1000006];
long long int pi[1000006];
long long int pp[1000006];
long long int ppi[1000006];
long long int ans = 0;
vector<long long int> c;
long long int r1, r0;
long long int powmod(long long int a, long long int b) {
  long long int an = 1;
  while (b > 0) {
    if ((b & 1)) an = (an * a) % 1000000007;
    b >>= 1;
    a = (a * a) % 1000000007;
  }
  return an;
}
long long int get(long long int l, long long int r) {
  long long int x = (h[r] - h[l - 1] + 1000000007) % 1000000007;
  x = (x * pi[l - 1]) % 1000000007;
  return x;
}
long long int get1(long long int l, long long int r) {
  long long int x = (hh[r] - hh[l - 1] + 1000000007) % 1000000007;
  x = (x * ppi[l - 1]) % 1000000007;
  return x;
}
void check(long long int x, long long int y) {
  long long int h0 = 0, h1 = 0, hh0, hh1;
  h0 = get(1, x);
  hh0 = get1(1, x);
  h1 = get(c[0] * x + 1, c[0] * x + y);
  hh1 = get1(c[0] * x + 1, c[0] * x + y);
  long long int cur = 1;
  long long int j = 0;
  long long int xx = c[0];
  bool z = 1;
  while (cur <= n) {
    if (j % 2) {
      if (get(cur, cur + y - 1) != h1 || get1(cur, cur + y - 1) != hh1) z = 0;
      cur += y;
      xx--;
    } else {
      if (get(cur, cur + x - 1) != h0 || get1(cur, cur + x - 1) != hh0) z = 0;
      cur += x;
      xx--;
    }
    if (xx == 0) {
      j++;
      xx = c[j];
    }
  }
  if (z && (h1 != h0 || hh1 != hh0)) ans++;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> s;
  cin >> t;
  if (s[0] == '1')
    for (auto &j : s)
      if (j == '1')
        j = '0';
      else
        j = '1';
  long long int i = 0, j = 0;
  while (i < s.length() && j < s.length()) {
    while (j < s.length() && s[i] == s[j]) j++;
    c.push_back(j - i);
    i = j;
  }
  p[0] = 1;
  for (int i = 1; i <= 1000000; i++) p[i] = (p[i - 1] * 101ll) % 1000000007;
  for (int i = 0; i <= 1000000; i++) pi[i] = powmod(p[i], 1000000007 - 2);
  pp[0] = 1;
  for (int i = 1; i <= 1000000; i++) pp[i] = (pp[i - 1] * 41ll) % 1000000007;
  for (int i = 0; i <= 1000000; i++) ppi[i] = powmod(pp[i], 1000000007 - 2);
  for (auto j : s)
    if (j == '0')
      c0++;
    else
      c1++;
  n = (int)t.length();
  for (int i = 1; i <= n; i++) {
    h[i] = (h[i - 1] + (t[i - 1] - 'a' + 1) * p[i]) % 1000000007;
    hh[i] = (hh[i - 1] + (t[i - 1] - 'a' + 1) * pp[i]) % 1000000007;
  }
  for (int i = 1; i <= n; i++) {
    long long int x = i;
    if (n - c0 * x <= 0 || (n - c0 * x) % c1 != 0) continue;
    check(i, (n - c0 * x) / c1);
  }
  cout << ans << '\n';
  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;
string s, t;
long long int c0, c1;
long long int n, m;
long long int h[1000006];
long long int hh[1000005];
long long int p[1000006];
long long int pi[1000006];
long long int pp[1000006];
long long int ppi[1000006];
long long int ans = 0;
vector<long long int> c;
long long int r1, r0;
long long int powmod(long long int a, long long int b) {
  long long int an = 1;
  while (b > 0) {
    if ((b & 1)) an = (an * a) % 1000000007;
    b >>= 1;
    a = (a * a) % 1000000007;
  }
  return an;
}
long long int get(long long int l, long long int r) {
  long long int x = (h[r] - h[l - 1] + 1000000007) % 1000000007;
  x = (x * pi[l - 1]) % 1000000007;
  return x;
}
long long int get1(long long int l, long long int r) {
  long long int x = (hh[r] - hh[l - 1] + 1000000007) % 1000000007;
  x = (x * ppi[l - 1]) % 1000000007;
  return x;
}
void check(long long int x, long long int y) {
  long long int h0 = 0, h1 = 0, hh0, hh1;
  h0 = get(1, x);
  hh0 = get1(1, x);
  h1 = get(c[0] * x + 1, c[0] * x + y);
  hh1 = get1(c[0] * x + 1, c[0] * x + y);
  long long int cur = 1;
  long long int j = 0;
  long long int xx = c[0];
  bool z = 1;
  while (cur <= n) {
    if (j % 2) {
      if (get(cur, cur + y - 1) != h1 || get1(cur, cur + y - 1) != hh1) z = 0;
      cur += y;
      xx--;
    } else {
      if (get(cur, cur + x - 1) != h0 || get1(cur, cur + x - 1) != hh0) z = 0;
      cur += x;
      xx--;
    }
    if (xx == 0) {
      j++;
      xx = c[j];
    }
  }
  if (z && (h1 != h0 || hh1 != hh0)) ans++;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> s;
  cin >> t;
  if (s[0] == '1')
    for (auto &j : s)
      if (j == '1')
        j = '0';
      else
        j = '1';
  long long int i = 0, j = 0;
  while (i < s.length() && j < s.length()) {
    while (j < s.length() && s[i] == s[j]) j++;
    c.push_back(j - i);
    i = j;
  }
  p[0] = 1;
  for (int i = 1; i <= 1000000; i++) p[i] = (p[i - 1] * 101ll) % 1000000007;
  for (int i = 0; i <= 1000000; i++) pi[i] = powmod(p[i], 1000000007 - 2);
  pp[0] = 1;
  for (int i = 1; i <= 1000000; i++) pp[i] = (pp[i - 1] * 41ll) % 1000000007;
  for (int i = 0; i <= 1000000; i++) ppi[i] = powmod(pp[i], 1000000007 - 2);
  for (auto j : s)
    if (j == '0')
      c0++;
    else
      c1++;
  n = (int)t.length();
  for (int i = 1; i <= n; i++) {
    h[i] = (h[i - 1] + (t[i - 1] - 'a' + 1) * p[i]) % 1000000007;
    hh[i] = (hh[i - 1] + (t[i - 1] - 'a' + 1) * pp[i]) % 1000000007;
  }
  for (int i = 1; i <= n; i++) {
    long long int x = i;
    if (n - c0 * x <= 0 || (n - c0 * x) % c1 != 0) continue;
    check(i, (n - c0 * x) / c1);
  }
  cout << ans << '\n';
  return 0;
}

```