#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const long double pi = acos(-1.0);
const long double log23 = 1.58496250072115618145373894394781;
const long double eps = 1e-8;
const long long INF = 1e18 + 239;
const long long prost = 239;
const int two = 2;
const int th = 3;
const long long MOD = 1e9 + 7;
const long long MOD2 = MOD * MOD;
const int BIG = 1e9 + 239;
const int alf = 26;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int dxb[4] = {-1, 1, 1, -1};
const int dyb[4] = {-1, 1, -1, 1};
const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int dig = 10;
const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
const long long bt = 30;
template <typename T>
inline T gcd(T a, T b) {
  while (a) {
    b %= a;
    swap(a, b);
  }
  return b;
}
template <typename T>
inline T lcm(T a, T b) {
  return (a / gcd(a, b)) * b;
}
inline bool is_down(char x) { return ('a' <= x && x <= 'z'); }
inline bool is_upper(char x) { return ('A' <= x && x <= 'Z'); }
inline bool is_digit(char x) { return ('0' <= x && x <= '9'); }
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int M = 1e6 + 239;
const int N = 2e3 + 239;
const int L = 19;
const int T = (1 << 19);
const int B = trunc(sqrt(M)) + 1;
const int X = 110;
string s, t;
int n, m, c[two];
long long pref[two][M], st[two][M], mod[two], pr[two];
long long gethash(int l, int r) {
  long long h1 = (pref[0][r + 1] - pref[0][l] * st[0][r - l + 1]) % mod[0];
  long long h2 = (pref[1][r + 1] - pref[1][l] * st[1][r - l + 1]) % mod[1];
  if (h1 < 0) h1 += mod[0];
  if (h2 < 0) h2 += mod[1];
  return ((h1 << 31LL) | h2);
}
bool check(int l0, int l1) {
  set<long long> q0, q1;
  int l = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == '0') {
      long long nw = gethash(l, l + l0 - 1);
      q0.insert(nw);
      if (q0.size() > 1) return false;
      l += l0;
    } else {
      long long nw = gethash(l, l + l1 - 1);
      q1.insert(nw);
      if (q1.size() > 1) return false;
      l += l1;
    }
  }
  if (*q0.begin() == *q1.begin()) return false;
  return true;
}
bool is_prime(int x) {
  for (int i = 2; i * i <= x; i++)
    if (x % i == 0) return false;
  return true;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int pos = (abs((int)rnd()) % 600000000) + 600000000;
  vector<int> md;
  while (md.size() < 2) {
    if (is_prime(pos)) md.push_back(pos);
    pos--;
  }
  mod[0] = md[0];
  mod[1] = md[1];
  pr[0] = (abs((long long)rnd()) % (mod[0] - 1000)) + 239;
  pr[1] = (abs((long long)rnd()) % (mod[1] - 1000)) + 239;
  cin >> s >> t;
  n = (int)s.size();
  m = (int)t.size();
  for (int c = 0; c < 2; c++) {
    st[c][0] = 1;
    for (int x = 0; x < m; x++) st[c][x + 1] = (st[c][x] * pr[c]) % mod[c];
    pref[c][0] = 0;
    for (int x = 0; x < m; x++)
      pref[c][x + 1] = (pref[c][x] * pr[c] + (t[x] - 'a' + 1)) % mod[c];
  }
  c[0] = c[1] = 0;
  for (int i = 0; i < n; i++) c[s[i] - '0']++;
  int ans = 0;
  for (int l0 = 1; l0 <= m; l0++) {
    if ((long long)m <= (long long)l0 * (long long)c[0]) break;
    int l1 = m - l0 * c[0];
    if (l1 % c[1] == 0) {
      l1 /= c[1];
      ans += check(l0, l1);
      continue;
    }
  }
  cout << ans;
  return 0;
}

### Prompt

Your challenge is to write 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("O3")
using namespace std;
const long double pi = acos(-1.0);
const long double log23 = 1.58496250072115618145373894394781;
const long double eps = 1e-8;
const long long INF = 1e18 + 239;
const long long prost = 239;
const int two = 2;
const int th = 3;
const long long MOD = 1e9 + 7;
const long long MOD2 = MOD * MOD;
const int BIG = 1e9 + 239;
const int alf = 26;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int dxb[4] = {-1, 1, 1, -1};
const int dyb[4] = {-1, 1, -1, 1};
const int dxo[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dyo[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
const int dig = 10;
const int day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int digarr[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
const long long bt = 30;
template <typename T>
inline T gcd(T a, T b) {
  while (a) {
    b %= a;
    swap(a, b);
  }
  return b;
}
template <typename T>
inline T lcm(T a, T b) {
  return (a / gcd(a, b)) * b;
}
inline bool is_down(char x) { return ('a' <= x && x <= 'z'); }
inline bool is_upper(char x) { return ('A' <= x && x <= 'Z'); }
inline bool is_digit(char x) { return ('0' <= x && x <= '9'); }
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int M = 1e6 + 239;
const int N = 2e3 + 239;
const int L = 19;
const int T = (1 << 19);
const int B = trunc(sqrt(M)) + 1;
const int X = 110;
string s, t;
int n, m, c[two];
long long pref[two][M], st[two][M], mod[two], pr[two];
long long gethash(int l, int r) {
  long long h1 = (pref[0][r + 1] - pref[0][l] * st[0][r - l + 1]) % mod[0];
  long long h2 = (pref[1][r + 1] - pref[1][l] * st[1][r - l + 1]) % mod[1];
  if (h1 < 0) h1 += mod[0];
  if (h2 < 0) h2 += mod[1];
  return ((h1 << 31LL) | h2);
}
bool check(int l0, int l1) {
  set<long long> q0, q1;
  int l = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == '0') {
      long long nw = gethash(l, l + l0 - 1);
      q0.insert(nw);
      if (q0.size() > 1) return false;
      l += l0;
    } else {
      long long nw = gethash(l, l + l1 - 1);
      q1.insert(nw);
      if (q1.size() > 1) return false;
      l += l1;
    }
  }
  if (*q0.begin() == *q1.begin()) return false;
  return true;
}
bool is_prime(int x) {
  for (int i = 2; i * i <= x; i++)
    if (x % i == 0) return false;
  return true;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int pos = (abs((int)rnd()) % 600000000) + 600000000;
  vector<int> md;
  while (md.size() < 2) {
    if (is_prime(pos)) md.push_back(pos);
    pos--;
  }
  mod[0] = md[0];
  mod[1] = md[1];
  pr[0] = (abs((long long)rnd()) % (mod[0] - 1000)) + 239;
  pr[1] = (abs((long long)rnd()) % (mod[1] - 1000)) + 239;
  cin >> s >> t;
  n = (int)s.size();
  m = (int)t.size();
  for (int c = 0; c < 2; c++) {
    st[c][0] = 1;
    for (int x = 0; x < m; x++) st[c][x + 1] = (st[c][x] * pr[c]) % mod[c];
    pref[c][0] = 0;
    for (int x = 0; x < m; x++)
      pref[c][x + 1] = (pref[c][x] * pr[c] + (t[x] - 'a' + 1)) % mod[c];
  }
  c[0] = c[1] = 0;
  for (int i = 0; i < n; i++) c[s[i] - '0']++;
  int ans = 0;
  for (int l0 = 1; l0 <= m; l0++) {
    if ((long long)m <= (long long)l0 * (long long)c[0]) break;
    int l1 = m - l0 * c[0];
    if (l1 % c[1] == 0) {
      l1 /= c[1];
      ans += check(l0, l1);
      continue;
    }
  }
  cout << ans;
  return 0;
}

```