#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 9;
const long long base = 73;
const int maxn = 1e6 + 10;
long long p[maxn];
int main() {
  string s, t;
  cin >> s >> t;
  int cnt[2] = {0, 0};
  int pr[2][s.length() + 1];
  pr[0][0] = pr[1][0] = 0;
  vector<int> v[2];
  for (int i = 0; i < s.length(); i++) {
    pr[0][i + 1] = pr[0][i];
    pr[1][i + 1] = pr[1][i];
    cnt[s[i] - '0']++;
    pr[s[i] - '0'][i + 1]++;
    v[s[i] - '0'].push_back(i + 1);
  }
  int len = t.length();
  long long hash[len + 1];
  hash[0] = 0;
  p[0] = 1;
  for (int i = 1; i < maxn; i++) {
    p[i] = (p[i - 1] * base) % mod;
  }
  for (int i = 1; i <= len; i++) {
    hash[i] =
        (((hash[i - 1] + p[i - 1] * (t[i - 1] - 'a' + 1) % mod) % mod) + mod) %
        mod;
  }
  int ans = 0;
  for (int i = 1; i <= len / cnt[s[0] - '0']; i++) {
    int ln[2];
    ln[s[0] - '0'] = i;
    ln[1 - (s[0] - '0')] =
        (len - cnt[s[0] - '0'] * ln[s[0] - '0']) / cnt[1 - (s[0] - '0')];
    if (ln[1] * cnt[1] + ln[0] * cnt[0] != len or ln[0] == 0 or ln[1] == 0)
      continue;
    long long hsh[2];
    hsh[s[0] - '0'] = ((p[len + 1 - i] * hash[i] % mod) + mod) % mod;
    int pos = v[1 - (s[0] - '0')][0] - 1;
    int l = pos * i + 1;
    int r = l + ln[1 - (s[0] - '0')] - 1;
    hsh[1 - (s[0] - '0')] =
        ((p[len + 1 - r] * (hash[r] - hash[l - 1]) % mod) + mod) % mod;
    if (hsh[0] == hsh[1]) continue;
    bool ok = true;
    for (int j = 0; j < 2; j++) {
      for (int x : v[j]) {
        int l = pr[0][x - 1] * ln[0] + pr[1][x - 1] * ln[1] + 1;
        int r = l + ln[j] - 1;
        ok &= hsh[j] ==
              ((p[len + 1 - r] * (hash[r] - hash[l - 1]) % mod) + mod) % mod;
      }
    }
    ans += ok;
  }
  cout << ans << endl;
  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;
const long long mod = 1e9 + 9;
const long long base = 73;
const int maxn = 1e6 + 10;
long long p[maxn];
int main() {
  string s, t;
  cin >> s >> t;
  int cnt[2] = {0, 0};
  int pr[2][s.length() + 1];
  pr[0][0] = pr[1][0] = 0;
  vector<int> v[2];
  for (int i = 0; i < s.length(); i++) {
    pr[0][i + 1] = pr[0][i];
    pr[1][i + 1] = pr[1][i];
    cnt[s[i] - '0']++;
    pr[s[i] - '0'][i + 1]++;
    v[s[i] - '0'].push_back(i + 1);
  }
  int len = t.length();
  long long hash[len + 1];
  hash[0] = 0;
  p[0] = 1;
  for (int i = 1; i < maxn; i++) {
    p[i] = (p[i - 1] * base) % mod;
  }
  for (int i = 1; i <= len; i++) {
    hash[i] =
        (((hash[i - 1] + p[i - 1] * (t[i - 1] - 'a' + 1) % mod) % mod) + mod) %
        mod;
  }
  int ans = 0;
  for (int i = 1; i <= len / cnt[s[0] - '0']; i++) {
    int ln[2];
    ln[s[0] - '0'] = i;
    ln[1 - (s[0] - '0')] =
        (len - cnt[s[0] - '0'] * ln[s[0] - '0']) / cnt[1 - (s[0] - '0')];
    if (ln[1] * cnt[1] + ln[0] * cnt[0] != len or ln[0] == 0 or ln[1] == 0)
      continue;
    long long hsh[2];
    hsh[s[0] - '0'] = ((p[len + 1 - i] * hash[i] % mod) + mod) % mod;
    int pos = v[1 - (s[0] - '0')][0] - 1;
    int l = pos * i + 1;
    int r = l + ln[1 - (s[0] - '0')] - 1;
    hsh[1 - (s[0] - '0')] =
        ((p[len + 1 - r] * (hash[r] - hash[l - 1]) % mod) + mod) % mod;
    if (hsh[0] == hsh[1]) continue;
    bool ok = true;
    for (int j = 0; j < 2; j++) {
      for (int x : v[j]) {
        int l = pr[0][x - 1] * ln[0] + pr[1][x - 1] * ln[1] + 1;
        int r = l + ln[j] - 1;
        ok &= hsh[j] ==
              ((p[len + 1 - r] * (hash[r] - hash[l - 1]) % mod) + mod) % mod;
      }
    }
    ans += ok;
  }
  cout << ans << endl;
  return 0;
}

```