#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 20;
const int mod[] = {1000 * 1000 * 1000 + 7, 1000 * 1000 * 1000 + 9};
const int base[] = {737, 4001};
int t[2];
array<int, 2> pw[maxn], h[maxn];
void prepare() {
  for (int j = 0; j < 2; j++) {
    pw[0][j] = 1;
    for (int i = 1; i < maxn; i++)
      pw[i][j] = 1LL * pw[i - 1][j] * base[j] % mod[j];
  }
}
inline int get(int l, int r, int k) {
  int ans =
      (h[r][k] - (1LL * h[l][k] * pw[r - l][k] % mod[k]) + mod[k]) % mod[k];
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  prepare();
  string s, tx;
  cin >> s >> tx;
  int n = s.size(), m = tx.size();
  for (int i = 0; i < m; i++)
    for (int j = 0; j < 2; j++)
      h[i + 1][j] = (1LL * h[i][j] * base[j] + tx[i]) % mod[j];
  for (auto ch : s) t[ch - '0']++;
  int res = 0;
  for (int sz0 = 1; sz0 * t[0] < m; sz0++) {
    int sz1 = (m - sz0 * t[0]) / t[1];
    if (sz0 * t[0] + sz1 * t[1] != m) continue;
    int sum = 0, f = 1;
    array<int, 2> h0, h1;
    bool is0 = 0, is1 = 0;
    for (int i = 0; i < n; i++) {
      if (s[i] == '0') {
        array<int, 2> tmp;
        for (int j = 0; j < 2; j++) tmp[j] = get(sum, sum + sz0, j);
        if (is0) {
          for (int j = 0; j < 2; j++)
            if (h0[j] != tmp[j]) f = 0;
        } else
          h0 = tmp;
        is0 = 1;
        sum += sz0;
      } else {
        array<int, 2> tmp;
        for (int j = 0; j < 2; j++) tmp[j] = get(sum, sum + sz1, j);
        if (is1) {
          for (int j = 0; j < 2; j++)
            if (h1[j] != tmp[j]) f = 0;
        } else
          h1 = tmp;
        is1 = 1;
        sum += sz1;
      }
    }
    if (h0 == h1) f = 0;
    res += f;
  }
  cout << res << endl;
}

### Prompt

Develop a solution in cpp 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 int maxn = 1e6 + 20;
const int mod[] = {1000 * 1000 * 1000 + 7, 1000 * 1000 * 1000 + 9};
const int base[] = {737, 4001};
int t[2];
array<int, 2> pw[maxn], h[maxn];
void prepare() {
  for (int j = 0; j < 2; j++) {
    pw[0][j] = 1;
    for (int i = 1; i < maxn; i++)
      pw[i][j] = 1LL * pw[i - 1][j] * base[j] % mod[j];
  }
}
inline int get(int l, int r, int k) {
  int ans =
      (h[r][k] - (1LL * h[l][k] * pw[r - l][k] % mod[k]) + mod[k]) % mod[k];
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  prepare();
  string s, tx;
  cin >> s >> tx;
  int n = s.size(), m = tx.size();
  for (int i = 0; i < m; i++)
    for (int j = 0; j < 2; j++)
      h[i + 1][j] = (1LL * h[i][j] * base[j] + tx[i]) % mod[j];
  for (auto ch : s) t[ch - '0']++;
  int res = 0;
  for (int sz0 = 1; sz0 * t[0] < m; sz0++) {
    int sz1 = (m - sz0 * t[0]) / t[1];
    if (sz0 * t[0] + sz1 * t[1] != m) continue;
    int sum = 0, f = 1;
    array<int, 2> h0, h1;
    bool is0 = 0, is1 = 0;
    for (int i = 0; i < n; i++) {
      if (s[i] == '0') {
        array<int, 2> tmp;
        for (int j = 0; j < 2; j++) tmp[j] = get(sum, sum + sz0, j);
        if (is0) {
          for (int j = 0; j < 2; j++)
            if (h0[j] != tmp[j]) f = 0;
        } else
          h0 = tmp;
        is0 = 1;
        sum += sz0;
      } else {
        array<int, 2> tmp;
        for (int j = 0; j < 2; j++) tmp[j] = get(sum, sum + sz1, j);
        if (is1) {
          for (int j = 0; j < 2; j++)
            if (h1[j] != tmp[j]) f = 0;
        } else
          h1 = tmp;
        is1 = 1;
        sum += sz1;
      }
    }
    if (h0 == h1) f = 0;
    res += f;
  }
  cout << res << endl;
}

```