#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "inline", "no-stack-protector")
using namespace std;
long long read() {
  long long x;
  char c(getchar());
  bool k;
  while (!isdigit(c) && c ^ '-')
    if ((c = getchar()) == EOF) exit(0);
  if (c ^ '-')
    k = 1, x = c & 15;
  else
    k = x = 0;
  while (isdigit((c = getchar()))) x = (x << 1) + (x << 3) + (c & 15);
  return k ? x : -x;
}
void wr(long long a) {
  if (a < 0) putchar('-'), a = -a;
  if (a <= 9)
    putchar(a | '0');
  else
    wr(a / 10), putchar((a % 10) | '0');
}
signed const INF(0x3f3f3f3f), NINF(0xc3c3c3c3);
long long const LINF(0x3f3f3f3f3f3f3f3fLL), LNINF(0xc3c3c3c3c3c3c3c3LL);
long long n, m, ans, lm, s0, s1, h[(1000010)], pw[(1000010)]{1};
char s[(1000010)], t[(1000010)];
void slv(long long a, long long b);
signed main() {
  cin >> s + 1, n = strlen(s + 1);
  for (long long i(1); i <= (n); ++i) s[i] & 1 ? ++s1 : ++s0;
  cin >> t + 1, m = strlen(t + 1), lm = (m - s1) / s0;
  for (long long i(1); i <= (m); ++i)
    pw[i] = pw[i - 1] * (97) % (992844353),
    h[i] = (h[i - 1] * (97) + t[i]) % (992844353);
  for (long long i(1); i <= (lm); ++i)
    if (!((m - s0 * i) % s1)) slv(i, (m - s0 * i) / s1);
  wr(ans), exit(0);
}
void slv(long long a, long long b) {
  long long l(0), h0, h1;
  bool f0(0), f1(0);
  for (long long i(1); i <= (n); ++i) {
    if (s[i] & 1) {
      if (f1) {
        if ((h[l + b] - h[l] * pw[b] % (992844353) + (992844353)) %
                (992844353) !=
            h1)
          return;
      } else
        h1 =
            (h[l + b] - h[l] * pw[b] % (992844353) + (992844353)) % (992844353),
        f1 = 1;
      l += b;
    } else {
      if (f0) {
        if ((h[l + a] - h[l] * pw[a] % (992844353) + (992844353)) %
                (992844353) !=
            h0)
          return;
      } else
        h0 =
            (h[l + a] - h[l] * pw[a] % (992844353) + (992844353)) % (992844353),
        f0 = 1;
      l += a;
    }
    if (a == b && f0 && f1 && h0 == h1) return;
  }
  ++ans;
}

### 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>
#pragma GCC optimize("Ofast", "inline", "no-stack-protector")
using namespace std;
long long read() {
  long long x;
  char c(getchar());
  bool k;
  while (!isdigit(c) && c ^ '-')
    if ((c = getchar()) == EOF) exit(0);
  if (c ^ '-')
    k = 1, x = c & 15;
  else
    k = x = 0;
  while (isdigit((c = getchar()))) x = (x << 1) + (x << 3) + (c & 15);
  return k ? x : -x;
}
void wr(long long a) {
  if (a < 0) putchar('-'), a = -a;
  if (a <= 9)
    putchar(a | '0');
  else
    wr(a / 10), putchar((a % 10) | '0');
}
signed const INF(0x3f3f3f3f), NINF(0xc3c3c3c3);
long long const LINF(0x3f3f3f3f3f3f3f3fLL), LNINF(0xc3c3c3c3c3c3c3c3LL);
long long n, m, ans, lm, s0, s1, h[(1000010)], pw[(1000010)]{1};
char s[(1000010)], t[(1000010)];
void slv(long long a, long long b);
signed main() {
  cin >> s + 1, n = strlen(s + 1);
  for (long long i(1); i <= (n); ++i) s[i] & 1 ? ++s1 : ++s0;
  cin >> t + 1, m = strlen(t + 1), lm = (m - s1) / s0;
  for (long long i(1); i <= (m); ++i)
    pw[i] = pw[i - 1] * (97) % (992844353),
    h[i] = (h[i - 1] * (97) + t[i]) % (992844353);
  for (long long i(1); i <= (lm); ++i)
    if (!((m - s0 * i) % s1)) slv(i, (m - s0 * i) / s1);
  wr(ans), exit(0);
}
void slv(long long a, long long b) {
  long long l(0), h0, h1;
  bool f0(0), f1(0);
  for (long long i(1); i <= (n); ++i) {
    if (s[i] & 1) {
      if (f1) {
        if ((h[l + b] - h[l] * pw[b] % (992844353) + (992844353)) %
                (992844353) !=
            h1)
          return;
      } else
        h1 =
            (h[l + b] - h[l] * pw[b] % (992844353) + (992844353)) % (992844353),
        f1 = 1;
      l += b;
    } else {
      if (f0) {
        if ((h[l + a] - h[l] * pw[a] % (992844353) + (992844353)) %
                (992844353) !=
            h0)
          return;
      } else
        h0 =
            (h[l + a] - h[l] * pw[a] % (992844353) + (992844353)) % (992844353),
        f0 = 1;
      l += a;
    }
    if (a == b && f0 && f1 && h0 == h1) return;
  }
  ++ans;
}

```