#include <bits/stdc++.h>
using namespace std;
inline int in() {
  int x;
  scanf("%d", &x);
  return x;
}
template <typename T>
inline istream& operator>>(istream& i, vector<T>& v) {
  for (int j = 0; j < ((int)(v).size()); ++j) i >> v[j];
  return i;
}
template <typename T>
string join(const vector<T>& v) {
  stringstream s;
  for (int i = 0; i < ((int)(v).size()); ++i) s << ' ' << v[i];
  return s.str().substr(1);
}
template <typename T>
inline ostream& operator<<(ostream& o, const vector<T>& v) {
  if ((int)(v).size()) o << join(v);
  return o;
}
template <typename T1, typename T2>
inline istream& operator>>(istream& i, pair<T1, T2>& v) {
  return i >> v.first >> v.second;
}
template <typename T1, typename T2>
inline ostream& operator<<(ostream& o, const pair<T1, T2>& v) {
  return o << v.first << "," << v.second;
}
template <typename T>
inline long long int suma(const vector<T>& a) {
  long long int res(0);
  for (auto&& x : a) res += x;
  return res;
}
const double eps = 1e-10;
const long long int LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MX = 200005;
const int p1 = 33487;
struct mints {
  template <int mod>
  struct mint {
    long long int x;
    mint(long long int x = 0) : x(x) {}
    mint& operator+=(const mint& a) {
      if ((x += a.x) >= mod) x -= mod;
      return *this;
    }
    mint& operator-=(const mint& a) {
      if ((x += mod - a.x) >= mod) x -= mod;
      return *this;
    }
    mint& operator*=(const mint& a) {
      (x *= a.x) %= mod;
      return *this;
    }
    mint& operator/=(const mint& a) {
      (x *= a.ex(mod - 2).x) %= mod;
      return *this;
    }
    mint operator+(const mint& a) const { return mint(*this) += a; }
    mint operator-(const mint& a) const { return mint(*this) -= a; }
    mint operator*(const mint& a) const { return mint(*this) *= a; }
    mint operator/(const mint& a) const { return mint(*this) /= a; }
    bool operator<(const mint& a) const { return x < a.x; }
    bool operator==(const mint& a) const { return x == a.x; }
    mint ex(long long int t) const {
      if (!t) return 1;
      mint res = ex(t / 2);
      res *= res;
      return (t & 1) ? res * x : res;
    }
  };
  mint<1011235817> x;
  mint<987654347> y;
  mints(long long int x = 0) : x(x), y(x) {}
  mints& operator+=(const mints& a) {
    x += a.x;
    y += a.y;
    return *this;
  }
  mints& operator-=(const mints& a) {
    x -= a.x;
    y -= a.y;
    return *this;
  }
  mints& operator*=(const mints& a) {
    x *= a.x;
    y *= a.y;
    return *this;
  }
  mints& operator/=(const mints& a) {
    x /= a.x;
    y /= a.y;
    return *this;
  }
  mints operator+(const mints& a) const { return mints(*this) += a; }
  mints operator-(const mints& a) const { return mints(*this) -= a; }
  mints operator*(const mints& a) const { return mints(*this) *= a; }
  mints operator/(const mints& a) const { return mints(*this) /= a; }
  bool operator<(const mints& a) const {
    return (x == a.x) ? (y < a.y) : (x < a.x);
  }
  bool operator==(const mints& a) const { return x == a.x && y == a.y; }
};
ostream& operator<<(ostream& o, const mints& a) {
  o << a.x.x * int(1e9) + a.y.x;
  return o;
}
int main() {
  string s, t;
  cin >> s >> t;
  int n = (int)(s).size();
  int m = (int)(t).size();
  vector<int> c(2);
  vector<int> a(n);
  for (int i = 0; i < (n); ++i) a[i] = s[i] - '0';
  for (int i = 0; i < (n); ++i) c[a[i]]++;
  if (c[0] < c[1]) {
    reverse(c.begin(), c.end());
    for (int i = 0; i < (n); ++i) a[i] ^= 1;
  }
  int mx = (m - c[1]) / c[0];
  vector<mints> d(m + 1);
  d[0] = 1;
  for (int i = 0; i < (m); ++i) d[i + 1] = d[i] * p1 + t[i];
  vector<mints> x(m + 1);
  x[0] = 1;
  for (int i = 0; i < (m); ++i) x[i + 1] = x[i] * p1;
  auto get = [&](int i, int w) { return d[i + w] - d[i] * x[w]; };
  int ans = 0;
  for (int l = 1; l <= (mx); ++l) {
    int r = m - l * c[0];
    if (r % c[1]) continue;
    r /= c[1];
    vector<int> w = {l, r};
    vector<int> e(2, -1);
    int p = 0;
    bool ok = true;
    for (int i = 0; i < (n); ++i) {
      if (e[a[i]] == -1) {
        e[a[i]] = p;
      } else {
        if (get(e[a[i]], w[a[i]]) == get(p, w[a[i]]))
          ;
        else {
          ok = false;
          break;
        }
      }
      p += w[a[i]];
    }
    if (ok && l == r && get(e[0], w[0]) == get(e[1], w[1])) ok = false;
    if (ok) ans++;
  }
  cout << ans << endl;
  return 0;
}

### 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;
inline int in() {
  int x;
  scanf("%d", &x);
  return x;
}
template <typename T>
inline istream& operator>>(istream& i, vector<T>& v) {
  for (int j = 0; j < ((int)(v).size()); ++j) i >> v[j];
  return i;
}
template <typename T>
string join(const vector<T>& v) {
  stringstream s;
  for (int i = 0; i < ((int)(v).size()); ++i) s << ' ' << v[i];
  return s.str().substr(1);
}
template <typename T>
inline ostream& operator<<(ostream& o, const vector<T>& v) {
  if ((int)(v).size()) o << join(v);
  return o;
}
template <typename T1, typename T2>
inline istream& operator>>(istream& i, pair<T1, T2>& v) {
  return i >> v.first >> v.second;
}
template <typename T1, typename T2>
inline ostream& operator<<(ostream& o, const pair<T1, T2>& v) {
  return o << v.first << "," << v.second;
}
template <typename T>
inline long long int suma(const vector<T>& a) {
  long long int res(0);
  for (auto&& x : a) res += x;
  return res;
}
const double eps = 1e-10;
const long long int LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MX = 200005;
const int p1 = 33487;
struct mints {
  template <int mod>
  struct mint {
    long long int x;
    mint(long long int x = 0) : x(x) {}
    mint& operator+=(const mint& a) {
      if ((x += a.x) >= mod) x -= mod;
      return *this;
    }
    mint& operator-=(const mint& a) {
      if ((x += mod - a.x) >= mod) x -= mod;
      return *this;
    }
    mint& operator*=(const mint& a) {
      (x *= a.x) %= mod;
      return *this;
    }
    mint& operator/=(const mint& a) {
      (x *= a.ex(mod - 2).x) %= mod;
      return *this;
    }
    mint operator+(const mint& a) const { return mint(*this) += a; }
    mint operator-(const mint& a) const { return mint(*this) -= a; }
    mint operator*(const mint& a) const { return mint(*this) *= a; }
    mint operator/(const mint& a) const { return mint(*this) /= a; }
    bool operator<(const mint& a) const { return x < a.x; }
    bool operator==(const mint& a) const { return x == a.x; }
    mint ex(long long int t) const {
      if (!t) return 1;
      mint res = ex(t / 2);
      res *= res;
      return (t & 1) ? res * x : res;
    }
  };
  mint<1011235817> x;
  mint<987654347> y;
  mints(long long int x = 0) : x(x), y(x) {}
  mints& operator+=(const mints& a) {
    x += a.x;
    y += a.y;
    return *this;
  }
  mints& operator-=(const mints& a) {
    x -= a.x;
    y -= a.y;
    return *this;
  }
  mints& operator*=(const mints& a) {
    x *= a.x;
    y *= a.y;
    return *this;
  }
  mints& operator/=(const mints& a) {
    x /= a.x;
    y /= a.y;
    return *this;
  }
  mints operator+(const mints& a) const { return mints(*this) += a; }
  mints operator-(const mints& a) const { return mints(*this) -= a; }
  mints operator*(const mints& a) const { return mints(*this) *= a; }
  mints operator/(const mints& a) const { return mints(*this) /= a; }
  bool operator<(const mints& a) const {
    return (x == a.x) ? (y < a.y) : (x < a.x);
  }
  bool operator==(const mints& a) const { return x == a.x && y == a.y; }
};
ostream& operator<<(ostream& o, const mints& a) {
  o << a.x.x * int(1e9) + a.y.x;
  return o;
}
int main() {
  string s, t;
  cin >> s >> t;
  int n = (int)(s).size();
  int m = (int)(t).size();
  vector<int> c(2);
  vector<int> a(n);
  for (int i = 0; i < (n); ++i) a[i] = s[i] - '0';
  for (int i = 0; i < (n); ++i) c[a[i]]++;
  if (c[0] < c[1]) {
    reverse(c.begin(), c.end());
    for (int i = 0; i < (n); ++i) a[i] ^= 1;
  }
  int mx = (m - c[1]) / c[0];
  vector<mints> d(m + 1);
  d[0] = 1;
  for (int i = 0; i < (m); ++i) d[i + 1] = d[i] * p1 + t[i];
  vector<mints> x(m + 1);
  x[0] = 1;
  for (int i = 0; i < (m); ++i) x[i + 1] = x[i] * p1;
  auto get = [&](int i, int w) { return d[i + w] - d[i] * x[w]; };
  int ans = 0;
  for (int l = 1; l <= (mx); ++l) {
    int r = m - l * c[0];
    if (r % c[1]) continue;
    r /= c[1];
    vector<int> w = {l, r};
    vector<int> e(2, -1);
    int p = 0;
    bool ok = true;
    for (int i = 0; i < (n); ++i) {
      if (e[a[i]] == -1) {
        e[a[i]] = p;
      } else {
        if (get(e[a[i]], w[a[i]]) == get(p, w[a[i]]))
          ;
        else {
          ok = false;
          break;
        }
      }
      p += w[a[i]];
    }
    if (ok && l == r && get(e[0], w[0]) == get(e[1], w[1])) ok = false;
    if (ok) ans++;
  }
  cout << ans << endl;
  return 0;
}

```