#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const long long inf = numeric_limits<long long>::max() / 2;
const long double eps = 1e-9;
const long double pi = acos(-1);
template <typename T>
inline bool mineq(T& a, T b) {
  return (a > b) ? (a = b, 1) : 0;
}
template <typename T>
inline bool maxeq(T& a, T b) {
  return (a < b) ? (a = b, 1) : 0;
}
inline void solve(), read();
const string file = "";
int main() {
  if (file != "") {
    freopen((file + ".in").c_str(), "r", stdin);
    freopen((file + ".out").c_str(), "w", stdout);
  }
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  ;
  read();
  solve();
  return 0;
}
const long long R = 998244353;
const long long P = 9937;
string s, t;
long long n, m;
vector<long long> pos[2];
vector<long long> pre[2];
vector<long long> hs, ps;
void precalc() {
  hs.resize(m);
  hs[0] = t[0];
  for (long long i = 1; i < m; i++) {
    hs[i] = hs[i - 1] * P % R + t[i];
    hs[i] %= R;
  }
  ps.resize(m + 1);
  ps[0] = 1;
  for (long long i = 1; i <= m; i++) {
    ps[i] = ps[i - 1] * P % R;
  }
}
long long gethash(long long l, long long r) {
  if (r >= m) {
    return -1;
  }
  if (l == 0) {
    return hs[r];
  }
  return (hs[r] - hs[l - 1] * ps[r - l + 1] % R + R) % R;
}
inline void solve() {
  precalc();
  long long c0 = 0, c1 = 0;
  for (long long i = 0; i < n; i++) {
    if (s[i] == '0') {
      ++c0;
      pos[0].push_back(i);
    } else {
      ++c1;
      pos[1].push_back(i);
    }
  }
  pre[0].assign(n, 0);
  pre[1].assign(n, 0);
  for (long long i = 0; i < n; i++) {
    if (i) {
      pre[0][i] = pre[0][i - 1];
      pre[1][i] = pre[1][i - 1];
    }
    if (s[i] == '0') {
      ++pre[0][i];
    } else {
      ++pre[1][i];
    }
    if (s[i] == '0') {
    }
  }
  long long ans = 0;
  for (long long r0 = 1; c0 * r0 < m; r0++) {
    if ((m - c0 * r0) % c1 != 0) {
      continue;
    }
    long long r1 = (m - c0 * r0) / c1;
    long long real;
    real = pre[0][pos[0][0]] * r0 + pre[1][pos[0][0]] * r1;
    long long h0 = gethash(real - r0, real - 1);
    real = pre[0][pos[1][0]] * r0 + pre[1][pos[1][0]] * r1;
    long long h1 = gethash(real - r1, real - 1);
    long long ok = h0 != h1;
    if (!ok) {
      continue;
    }
    for (long long j : pos[0]) {
      long long real = pre[0][j] * r0 + pre[1][j] * r1;
      long long h = gethash(real - r0, real - 1);
      if (h != h0) {
        ok = 0;
        break;
      }
    }
    if (!ok) {
      continue;
    }
    for (long long j : pos[1]) {
      long long real = pre[0][j] * r0 + pre[1][j] * r1;
      long long h = gethash(real - r1, real - 1);
      if (h != h1) {
        ok = 0;
        break;
      }
    }
    ans += ok;
  }
  cout << ans << "\n";
}
inline void read() {
  cin >> s >> t;
  n = (long long)((s).size()), m = (long long)((t).size());
}

### 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>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const long long inf = numeric_limits<long long>::max() / 2;
const long double eps = 1e-9;
const long double pi = acos(-1);
template <typename T>
inline bool mineq(T& a, T b) {
  return (a > b) ? (a = b, 1) : 0;
}
template <typename T>
inline bool maxeq(T& a, T b) {
  return (a < b) ? (a = b, 1) : 0;
}
inline void solve(), read();
const string file = "";
int main() {
  if (file != "") {
    freopen((file + ".in").c_str(), "r", stdin);
    freopen((file + ".out").c_str(), "w", stdout);
  }
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  ;
  read();
  solve();
  return 0;
}
const long long R = 998244353;
const long long P = 9937;
string s, t;
long long n, m;
vector<long long> pos[2];
vector<long long> pre[2];
vector<long long> hs, ps;
void precalc() {
  hs.resize(m);
  hs[0] = t[0];
  for (long long i = 1; i < m; i++) {
    hs[i] = hs[i - 1] * P % R + t[i];
    hs[i] %= R;
  }
  ps.resize(m + 1);
  ps[0] = 1;
  for (long long i = 1; i <= m; i++) {
    ps[i] = ps[i - 1] * P % R;
  }
}
long long gethash(long long l, long long r) {
  if (r >= m) {
    return -1;
  }
  if (l == 0) {
    return hs[r];
  }
  return (hs[r] - hs[l - 1] * ps[r - l + 1] % R + R) % R;
}
inline void solve() {
  precalc();
  long long c0 = 0, c1 = 0;
  for (long long i = 0; i < n; i++) {
    if (s[i] == '0') {
      ++c0;
      pos[0].push_back(i);
    } else {
      ++c1;
      pos[1].push_back(i);
    }
  }
  pre[0].assign(n, 0);
  pre[1].assign(n, 0);
  for (long long i = 0; i < n; i++) {
    if (i) {
      pre[0][i] = pre[0][i - 1];
      pre[1][i] = pre[1][i - 1];
    }
    if (s[i] == '0') {
      ++pre[0][i];
    } else {
      ++pre[1][i];
    }
    if (s[i] == '0') {
    }
  }
  long long ans = 0;
  for (long long r0 = 1; c0 * r0 < m; r0++) {
    if ((m - c0 * r0) % c1 != 0) {
      continue;
    }
    long long r1 = (m - c0 * r0) / c1;
    long long real;
    real = pre[0][pos[0][0]] * r0 + pre[1][pos[0][0]] * r1;
    long long h0 = gethash(real - r0, real - 1);
    real = pre[0][pos[1][0]] * r0 + pre[1][pos[1][0]] * r1;
    long long h1 = gethash(real - r1, real - 1);
    long long ok = h0 != h1;
    if (!ok) {
      continue;
    }
    for (long long j : pos[0]) {
      long long real = pre[0][j] * r0 + pre[1][j] * r1;
      long long h = gethash(real - r0, real - 1);
      if (h != h0) {
        ok = 0;
        break;
      }
    }
    if (!ok) {
      continue;
    }
    for (long long j : pos[1]) {
      long long real = pre[0][j] * r0 + pre[1][j] * r1;
      long long h = gethash(real - r1, real - 1);
      if (h != h1) {
        ok = 0;
        break;
      }
    }
    ans += ok;
  }
  cout << ans << "\n";
}
inline void read() {
  cin >> s >> t;
  n = (long long)((s).size()), m = (long long)((t).size());
}

```