#include <bits/stdc++.h>
using namespace std;
int const N = 100000, M = 1000000, md1 = 1e9 + 7, md2 = 1e9 + 9;
int bs1, bs2, bs1p[M + 1], bs2p[M + 1], n, m;
char s[N + 1], t[M + 2];
struct H {
  int v1, v2;
  H() : v1(0), v2(0) {}
  void operator+=(char c) {
    v1 = ((long long)v1 * bs1 + (c - 'a' + 1)) % md1;
    v2 = ((long long)v2 * bs2 + (c - 'a' + 1)) % md2;
  }
  H operator-(H const &o) const {
    H an;
    an.v1 = v1 - o.v1;
    if (an.v1 < 0) an.v1 += md1;
    an.v2 = v2 - o.v2;
    if (an.v2 < 0) an.v2 += md2;
    return an;
  }
  H operator<<(int x) {
    H an;
    an.v1 = (long long)v1 * bs1p[x] % md1;
    an.v2 = (long long)v2 * bs2p[x] % md2;
    return an;
  }
  bool operator==(H const &o) const { return v1 == o.v1 && v2 == o.v2; }
} h[M + 1];
H getH(int l, int r) { return h[r] - (h[l - 1] << r - l + 1); }
int main() {
  srand(time(0));
  bs1 = rand() % 30 + 30;
  bs1p[0] = 1;
  for (int i = 1; i < (int)(M + 1); ++i)
    bs1p[i] = (long long)bs1p[i - 1] * bs1 % md1;
  bs2 = rand() % 30 + 30;
  bs2p[0] = 1;
  for (int i = 1; i < (int)(M + 1); ++i)
    bs2p[i] = (long long)bs2p[i - 1] * bs2 % md2;
  scanf("%s%s", s, t + 1);
  n = strlen(s);
  m = strlen(t + 1);
  for (int i = 1; i < (int)(m + 1); ++i) h[i] = h[i - 1], h[i] += t[i];
  if (s[0] == '1')
    for (int i = 0; i < (int)(n); ++i) {
      if (s[i] == '0')
        s[i] = '1';
      else
        s[i] = '0';
    }
  int st = 0;
  while (s[st] == '0') ++st;
  int fr0 = 0, fr1;
  for (int i = 0; i < (int)(n); ++i)
    if (s[i] == '0') ++fr0;
  fr1 = n - fr0;
  int an = 0;
  for (int i = 1; i < (int)(m + 1); ++i) {
    long long zl = (long long)i * fr0;
    if (zl > m) break;
    int ol = m - zl;
    if (ol == 0) continue;
    if (ol % fr1 != 0) continue;
    int j = ol / fr1;
    H zh = getH(1, i), oh = getH(st * i + 1, st * i + j);
    if (zh == oh) continue;
    bool ok = true;
    int c = 1;
    for (int k = 0; k < (int)(n); ++k) {
      if (s[k] == '0') {
        if (!(getH(c, c + i - 1) == zh)) {
          ok = false;
          break;
        }
        c += i;
      } else {
        if (!(getH(c, c + j - 1) == oh)) {
          ok = false;
          break;
        }
        c += j;
      }
    }
    if (ok) ++an;
  }
  printf("%d\n", an);
}

### 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;
int const N = 100000, M = 1000000, md1 = 1e9 + 7, md2 = 1e9 + 9;
int bs1, bs2, bs1p[M + 1], bs2p[M + 1], n, m;
char s[N + 1], t[M + 2];
struct H {
  int v1, v2;
  H() : v1(0), v2(0) {}
  void operator+=(char c) {
    v1 = ((long long)v1 * bs1 + (c - 'a' + 1)) % md1;
    v2 = ((long long)v2 * bs2 + (c - 'a' + 1)) % md2;
  }
  H operator-(H const &o) const {
    H an;
    an.v1 = v1 - o.v1;
    if (an.v1 < 0) an.v1 += md1;
    an.v2 = v2 - o.v2;
    if (an.v2 < 0) an.v2 += md2;
    return an;
  }
  H operator<<(int x) {
    H an;
    an.v1 = (long long)v1 * bs1p[x] % md1;
    an.v2 = (long long)v2 * bs2p[x] % md2;
    return an;
  }
  bool operator==(H const &o) const { return v1 == o.v1 && v2 == o.v2; }
} h[M + 1];
H getH(int l, int r) { return h[r] - (h[l - 1] << r - l + 1); }
int main() {
  srand(time(0));
  bs1 = rand() % 30 + 30;
  bs1p[0] = 1;
  for (int i = 1; i < (int)(M + 1); ++i)
    bs1p[i] = (long long)bs1p[i - 1] * bs1 % md1;
  bs2 = rand() % 30 + 30;
  bs2p[0] = 1;
  for (int i = 1; i < (int)(M + 1); ++i)
    bs2p[i] = (long long)bs2p[i - 1] * bs2 % md2;
  scanf("%s%s", s, t + 1);
  n = strlen(s);
  m = strlen(t + 1);
  for (int i = 1; i < (int)(m + 1); ++i) h[i] = h[i - 1], h[i] += t[i];
  if (s[0] == '1')
    for (int i = 0; i < (int)(n); ++i) {
      if (s[i] == '0')
        s[i] = '1';
      else
        s[i] = '0';
    }
  int st = 0;
  while (s[st] == '0') ++st;
  int fr0 = 0, fr1;
  for (int i = 0; i < (int)(n); ++i)
    if (s[i] == '0') ++fr0;
  fr1 = n - fr0;
  int an = 0;
  for (int i = 1; i < (int)(m + 1); ++i) {
    long long zl = (long long)i * fr0;
    if (zl > m) break;
    int ol = m - zl;
    if (ol == 0) continue;
    if (ol % fr1 != 0) continue;
    int j = ol / fr1;
    H zh = getH(1, i), oh = getH(st * i + 1, st * i + j);
    if (zh == oh) continue;
    bool ok = true;
    int c = 1;
    for (int k = 0; k < (int)(n); ++k) {
      if (s[k] == '0') {
        if (!(getH(c, c + i - 1) == zh)) {
          ok = false;
          break;
        }
        c += i;
      } else {
        if (!(getH(c, c + j - 1) == oh)) {
          ok = false;
          break;
        }
        c += j;
      }
    }
    if (ok) ++an;
  }
  printf("%d\n", an);
}

```