#include <bits/stdc++.h>
using namespace std;
const int infint = 1e9;
const long long inf = 1e18;
const int MAXN = (int)1e6 + 7;
const int MOD = (int)1e9 + 7;
string s, t;
long long hsh[MAXN], base = 47, pwr[MAXN], pwr2[MAXN], base2 = 31, hsh2[MAXN];
pair<long long, long long> get(long long l, long long r) {
  long long ans = hsh[r];
  if (l) ans -= hsh[l - 1] * pwr[r - l + 1] % MOD;
  ans = (ans + MOD) % MOD;
  long long ans2 = hsh2[r];
  if (l) ans2 -= hsh2[l - 1] * pwr2[r - l + 1] % MOD;
  ans2 = (ans2 + MOD) % MOD;
  return {ans, ans2};
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> t >> s;
  if (t[0] == '1') {
    for (int i = 0; i < t.size(); i++) {
      if (t[i] == '1')
        t[i] = '0';
      else
        t[i] = '1';
    }
  }
  pwr[0] = 1, pwr2[0] = 1;
  for (int i = 1; i < MAXN; i++)
    pwr[i] = pwr[i - 1] * base % MOD, pwr2[i] = pwr2[i - 1] * base2 % MOD;
  hsh[0] = s[0] - 'a' + 1, hsh2[0] = s[0] - 'a' + 1;
  for (int i = 1; i < s.size(); i++)
    hsh[i] = hsh[i - 1] * base % MOD + (s[i] - 'a' + 1), hsh[i] %= MOD,
    hsh2[i] = hsh2[i - 1] * base2 % MOD + (s[i] - 'a' + 1), hsh2[i] %= MOD;
  int one = 0, zero = 0, fir = -1;
  for (int i = 0; i < t.size(); i++)
    if (t[i] == '1') {
      one++;
      if (fir == -1) fir = i;
    } else {
      zero++;
    }
  long long ans = 0;
  for (int i = 1; i < s.size(); i++) {
    long long r0 = i;
    long long j = (s.size() - r0 * zero);
    if (j <= 0 || j % one) continue;
    j /= one;
    long long r1 = j;
    pair<long long, long long> HSH_S = get(0, i - 1),
                               HSH_T = get(fir * r0, fir * r0 + r1 - 1);
    bool c = 1;
    long long ptr = 0;
    for (int j = 0; j < t.size(); j++) {
      if (t[j] == '0') {
        if (ptr + r0 > s.size() || get(ptr, ptr + r0 - 1) != HSH_S) {
          c = 0;
          break;
        }
        ptr += r0;
      } else {
        if (ptr + r1 > s.size() || get(ptr, ptr + r1 - 1) != HSH_T) {
          c = 0;
          break;
        }
        ptr += r1;
      }
    }
    if (c && HSH_S != HSH_T) ans++;
  }
  cout << ans;
}

### Prompt

Create a solution in Cpp for 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 int infint = 1e9;
const long long inf = 1e18;
const int MAXN = (int)1e6 + 7;
const int MOD = (int)1e9 + 7;
string s, t;
long long hsh[MAXN], base = 47, pwr[MAXN], pwr2[MAXN], base2 = 31, hsh2[MAXN];
pair<long long, long long> get(long long l, long long r) {
  long long ans = hsh[r];
  if (l) ans -= hsh[l - 1] * pwr[r - l + 1] % MOD;
  ans = (ans + MOD) % MOD;
  long long ans2 = hsh2[r];
  if (l) ans2 -= hsh2[l - 1] * pwr2[r - l + 1] % MOD;
  ans2 = (ans2 + MOD) % MOD;
  return {ans, ans2};
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> t >> s;
  if (t[0] == '1') {
    for (int i = 0; i < t.size(); i++) {
      if (t[i] == '1')
        t[i] = '0';
      else
        t[i] = '1';
    }
  }
  pwr[0] = 1, pwr2[0] = 1;
  for (int i = 1; i < MAXN; i++)
    pwr[i] = pwr[i - 1] * base % MOD, pwr2[i] = pwr2[i - 1] * base2 % MOD;
  hsh[0] = s[0] - 'a' + 1, hsh2[0] = s[0] - 'a' + 1;
  for (int i = 1; i < s.size(); i++)
    hsh[i] = hsh[i - 1] * base % MOD + (s[i] - 'a' + 1), hsh[i] %= MOD,
    hsh2[i] = hsh2[i - 1] * base2 % MOD + (s[i] - 'a' + 1), hsh2[i] %= MOD;
  int one = 0, zero = 0, fir = -1;
  for (int i = 0; i < t.size(); i++)
    if (t[i] == '1') {
      one++;
      if (fir == -1) fir = i;
    } else {
      zero++;
    }
  long long ans = 0;
  for (int i = 1; i < s.size(); i++) {
    long long r0 = i;
    long long j = (s.size() - r0 * zero);
    if (j <= 0 || j % one) continue;
    j /= one;
    long long r1 = j;
    pair<long long, long long> HSH_S = get(0, i - 1),
                               HSH_T = get(fir * r0, fir * r0 + r1 - 1);
    bool c = 1;
    long long ptr = 0;
    for (int j = 0; j < t.size(); j++) {
      if (t[j] == '0') {
        if (ptr + r0 > s.size() || get(ptr, ptr + r0 - 1) != HSH_S) {
          c = 0;
          break;
        }
        ptr += r0;
      } else {
        if (ptr + r1 > s.size() || get(ptr, ptr + r1 - 1) != HSH_T) {
          c = 0;
          break;
        }
        ptr += r1;
      }
    }
    if (c && HSH_S != HSH_T) ans++;
  }
  cout << ans;
}

```