#include <bits/stdc++.h>
using namespace std;
vector<long long> h1(2000005, 0), h2(2000005, 0);
vector<long long> pow1(2000005, 1), pow2(2000005, 1);
int main() {
  for (long long i = 1; i < (2000005); i++) {
    pow1[i] = pow1[i - 1] * (long long)31 % (long long)1000000009;
    pow2[i] = pow2[i - 1] * (long long)37 % (long long)1000000007;
  }
  string(s);
  cin >> (s);
  ;
  string(t);
  cin >> (t);
  ;
  long long n = t.size();
  for (long long i = 0; i < (n); i++) {
    h1[i + 1] = (h1[i] + (long long)(t[i] - 'a' + 1LL) * pow1[i] %
                             (long long)1000000009) %
                (long long)1000000009;
    h2[i + 1] = (h2[i] + (long long)(t[i] - 'a' + 1LL) * pow2[i] %
                             (long long)1000000007) %
                (long long)1000000007;
  }
  long long m = s.size(), c0 = 0, c1 = 0;
  for (long long i = 0; i < (m); i++)
    if (s[i] == '0')
      c0++;
    else
      c1++;
  long long count = 0;
  for (long long l1 = 1; l1 < (n); l1++) {
    long long t1 = c1 * l1;
    if ((n - t1) <= 0 || (n - t1) % c0) continue;
    long long l0 = (n - t1) / c0;
    long long j = 0, i = 0;
    pair<long long, long long> ha0 = {-1, -1}, ha1 = {-1, -1};
    while (i < m && j < n) {
      assert(i < m);
      if (s[i] == '0') {
        if (j + l0 > n) break;
        assert(j < n);
        assert(j + l0 < h1.size());
        assert(j >= 0);
        assert(l0 > 0);
        assert(l0 < n);
        assert(n - j - 1 >= 0);
        assert(n - j - 1 < 2000005);
        long long v1 = (h1[j + l0] - h1[j] + (long long)1000000009) %
                       (long long)1000000009 * pow1[n - j - 1] %
                       (long long)1000000009;
        long long v2 = (h2[j + l0] - h2[j] + (long long)1000000007) %
                       (long long)1000000007 * pow2[n - j - 1] %
                       (long long)1000000007;
        if (ha0 == make_pair(-1LL, -1LL)) {
          ha0 = {v1, v2};
        } else if (make_pair(v1, v2) != ha0)
          break;
        j += l0;
      } else {
        if (j + l1 > n) break;
        assert(j < n);
        assert(j + l1 < h1.size());
        assert(j >= 0);
        assert(l1 > 0);
        assert(l1 < n);
        assert(n - j - 1 >= 0);
        assert(n - j - 1 < 2000005);
        long long v1 = (h1[j + l1] - h1[j] + (long long)1000000009) %
                       (long long)1000000009 * pow1[n - j - 1] %
                       (long long)1000000009;
        long long v2 = (h2[j + l1] - h2[j] + (long long)1000000007) %
                       (long long)1000000007 * pow2[n - j - 1] %
                       (long long)1000000007;
        if (ha1 == make_pair(-1LL, -1LL)) {
          ha1 = {v1, v2};
        } else if (make_pair(v1, v2) != ha1)
          break;
        j += l1;
      }
      i++;
    }
    if (i == m && j == n && ha0 != ha1) count++;
  }
  printf("%lld\n", count);
  return 0;
}

### Prompt

Your task is to create 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;
vector<long long> h1(2000005, 0), h2(2000005, 0);
vector<long long> pow1(2000005, 1), pow2(2000005, 1);
int main() {
  for (long long i = 1; i < (2000005); i++) {
    pow1[i] = pow1[i - 1] * (long long)31 % (long long)1000000009;
    pow2[i] = pow2[i - 1] * (long long)37 % (long long)1000000007;
  }
  string(s);
  cin >> (s);
  ;
  string(t);
  cin >> (t);
  ;
  long long n = t.size();
  for (long long i = 0; i < (n); i++) {
    h1[i + 1] = (h1[i] + (long long)(t[i] - 'a' + 1LL) * pow1[i] %
                             (long long)1000000009) %
                (long long)1000000009;
    h2[i + 1] = (h2[i] + (long long)(t[i] - 'a' + 1LL) * pow2[i] %
                             (long long)1000000007) %
                (long long)1000000007;
  }
  long long m = s.size(), c0 = 0, c1 = 0;
  for (long long i = 0; i < (m); i++)
    if (s[i] == '0')
      c0++;
    else
      c1++;
  long long count = 0;
  for (long long l1 = 1; l1 < (n); l1++) {
    long long t1 = c1 * l1;
    if ((n - t1) <= 0 || (n - t1) % c0) continue;
    long long l0 = (n - t1) / c0;
    long long j = 0, i = 0;
    pair<long long, long long> ha0 = {-1, -1}, ha1 = {-1, -1};
    while (i < m && j < n) {
      assert(i < m);
      if (s[i] == '0') {
        if (j + l0 > n) break;
        assert(j < n);
        assert(j + l0 < h1.size());
        assert(j >= 0);
        assert(l0 > 0);
        assert(l0 < n);
        assert(n - j - 1 >= 0);
        assert(n - j - 1 < 2000005);
        long long v1 = (h1[j + l0] - h1[j] + (long long)1000000009) %
                       (long long)1000000009 * pow1[n - j - 1] %
                       (long long)1000000009;
        long long v2 = (h2[j + l0] - h2[j] + (long long)1000000007) %
                       (long long)1000000007 * pow2[n - j - 1] %
                       (long long)1000000007;
        if (ha0 == make_pair(-1LL, -1LL)) {
          ha0 = {v1, v2};
        } else if (make_pair(v1, v2) != ha0)
          break;
        j += l0;
      } else {
        if (j + l1 > n) break;
        assert(j < n);
        assert(j + l1 < h1.size());
        assert(j >= 0);
        assert(l1 > 0);
        assert(l1 < n);
        assert(n - j - 1 >= 0);
        assert(n - j - 1 < 2000005);
        long long v1 = (h1[j + l1] - h1[j] + (long long)1000000009) %
                       (long long)1000000009 * pow1[n - j - 1] %
                       (long long)1000000009;
        long long v2 = (h2[j + l1] - h2[j] + (long long)1000000007) %
                       (long long)1000000007 * pow2[n - j - 1] %
                       (long long)1000000007;
        if (ha1 == make_pair(-1LL, -1LL)) {
          ha1 = {v1, v2};
        } else if (make_pair(v1, v2) != ha1)
          break;
        j += l1;
      }
      i++;
    }
    if (i == m && j == n && ha0 != ha1) count++;
  }
  printf("%lld\n", count);
  return 0;
}

```