#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
const long long INF = 1e18L + 7;
template <class n, class second>
ostream &operator<<(ostream &p, pair<n, second> x) {
  return p << "<" << x.first << ", " << x.second << ">";
}
template <class n>
auto operator<<(ostream &p, n y) ->
    typename enable_if<!is_same<n, string>::value,
                       decltype(y.begin(), p)>::type {
  int o = 0;
  p << "{";
  for (auto c : y) {
    if (o++) p << ", ";
    p << c;
  }
  return p << "}";
}
void dor() { cerr << '\n'; }
template <class n, class... second>
void dor(n p, second... y) {
  cerr << p << " ";
  dor(y...);
}
template <class n, class second>
void mini(n &p, second y) {
  if (p > y) p = y;
}
template <class n, class second>
void maxi(n &p, second y) {
  if (p < y) p = y;
}
long long P = 31;
long long mod1 = 1e9 + 7;
long long mod2 = 1e9 + 696969;
const long long N = 1e6 + 7;
long long n, m, c0, c1;
string second, t;
long long h1[N];
long long h2[N];
long long pot1[N];
long long pot2[N];
bool prime(long long x) {
  for (long long i = 2; i * i <= x; ++i) {
    if (x % i == 0) return 0;
  }
  return 1;
}
bool equal(long long a, long long b, long long c, long long d) {
  long long v1 = ((h1[b] - h1[a - 1] + mod1) * pot1[N - b]) % mod1;
  long long v2 = ((h1[d] - h1[c - 1] + mod1) * pot1[N - d]) % mod1;
  long long u1 = ((h2[b] - h2[a - 1] + mod2) * pot2[N - b]) % mod2;
  long long u2 = ((h2[d] - h2[c - 1] + mod2) * pot2[N - d]) % mod2;
  return v1 == v2 && u1 == u2;
}
bool solve(long long len1) {
  long long len0 = (n - len1 * c1) / c0;
  if (len0 <= 0 || len1 <= 0 || n != len0 * c0 + len1 * c1) return 0;
  long long l0 = -1;
  long long l1 = -1;
  long long ind = 1;
  for (long long i = 1; i <= m; ++i) {
    if (t[i] == '0') {
      if (l0 == -1) {
        l0 = ind;
        ind += len0;
        continue;
      }
      if (!equal(l0, l0 + len0 - 1, ind, ind + len0 - 1)) return 0;
      l0 = ind;
      ind += len0;
    } else {
      if (l1 == -1) {
        l1 = ind;
        ind += len1;
        continue;
      }
      if (!equal(l1, l1 + len1 - 1, ind, ind + len1 - 1)) return 0;
      l1 = ind;
      ind += len1;
    }
  }
  if (equal(l1, l1 + len1 - 1, l0, l0 + len0 - 1)) return 0;
  return 1;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  mod1 += rand() % 10000;
  mod2 += rand() % 10000;
  while (!prime(mod1)) ++mod1;
  while (!prime(mod2)) ++mod2;
  pot1[0] = pot2[0] = 1;
  for (long long i = 1; i < N; ++i) {
    pot1[i] = pot1[i - 1] * P % mod1;
    pot2[i] = pot2[i - 1] * P % mod2;
  }
  cin >> t >> second;
  m = t.size();
  n = second.size();
  t = '#' + t;
  second = '#' + second;
  for (long long i = 1; i <= m; ++i) {
    if (t[i] == '0')
      ++c0;
    else
      ++c1;
  }
  for (long long i = 1; i <= n; ++i) {
    h1[i] = second[i] * pot1[i] + h1[i - 1];
    h1[i] %= mod1;
    h2[i] = second[i] * pot2[i] + h2[i - 1];
    h2[i] %= mod2;
  }
  long long ans = 0;
  for (long long i = 1; i <= n; ++i) {
    if (solve(i)) ++ans;
  }
  cout << ans << '\n';
}

### Prompt

In cpp, your task is to solve 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 inf = 1e9 + 7;
const long long INF = 1e18L + 7;
template <class n, class second>
ostream &operator<<(ostream &p, pair<n, second> x) {
  return p << "<" << x.first << ", " << x.second << ">";
}
template <class n>
auto operator<<(ostream &p, n y) ->
    typename enable_if<!is_same<n, string>::value,
                       decltype(y.begin(), p)>::type {
  int o = 0;
  p << "{";
  for (auto c : y) {
    if (o++) p << ", ";
    p << c;
  }
  return p << "}";
}
void dor() { cerr << '\n'; }
template <class n, class... second>
void dor(n p, second... y) {
  cerr << p << " ";
  dor(y...);
}
template <class n, class second>
void mini(n &p, second y) {
  if (p > y) p = y;
}
template <class n, class second>
void maxi(n &p, second y) {
  if (p < y) p = y;
}
long long P = 31;
long long mod1 = 1e9 + 7;
long long mod2 = 1e9 + 696969;
const long long N = 1e6 + 7;
long long n, m, c0, c1;
string second, t;
long long h1[N];
long long h2[N];
long long pot1[N];
long long pot2[N];
bool prime(long long x) {
  for (long long i = 2; i * i <= x; ++i) {
    if (x % i == 0) return 0;
  }
  return 1;
}
bool equal(long long a, long long b, long long c, long long d) {
  long long v1 = ((h1[b] - h1[a - 1] + mod1) * pot1[N - b]) % mod1;
  long long v2 = ((h1[d] - h1[c - 1] + mod1) * pot1[N - d]) % mod1;
  long long u1 = ((h2[b] - h2[a - 1] + mod2) * pot2[N - b]) % mod2;
  long long u2 = ((h2[d] - h2[c - 1] + mod2) * pot2[N - d]) % mod2;
  return v1 == v2 && u1 == u2;
}
bool solve(long long len1) {
  long long len0 = (n - len1 * c1) / c0;
  if (len0 <= 0 || len1 <= 0 || n != len0 * c0 + len1 * c1) return 0;
  long long l0 = -1;
  long long l1 = -1;
  long long ind = 1;
  for (long long i = 1; i <= m; ++i) {
    if (t[i] == '0') {
      if (l0 == -1) {
        l0 = ind;
        ind += len0;
        continue;
      }
      if (!equal(l0, l0 + len0 - 1, ind, ind + len0 - 1)) return 0;
      l0 = ind;
      ind += len0;
    } else {
      if (l1 == -1) {
        l1 = ind;
        ind += len1;
        continue;
      }
      if (!equal(l1, l1 + len1 - 1, ind, ind + len1 - 1)) return 0;
      l1 = ind;
      ind += len1;
    }
  }
  if (equal(l1, l1 + len1 - 1, l0, l0 + len0 - 1)) return 0;
  return 1;
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  mod1 += rand() % 10000;
  mod2 += rand() % 10000;
  while (!prime(mod1)) ++mod1;
  while (!prime(mod2)) ++mod2;
  pot1[0] = pot2[0] = 1;
  for (long long i = 1; i < N; ++i) {
    pot1[i] = pot1[i - 1] * P % mod1;
    pot2[i] = pot2[i - 1] * P % mod2;
  }
  cin >> t >> second;
  m = t.size();
  n = second.size();
  t = '#' + t;
  second = '#' + second;
  for (long long i = 1; i <= m; ++i) {
    if (t[i] == '0')
      ++c0;
    else
      ++c1;
  }
  for (long long i = 1; i <= n; ++i) {
    h1[i] = second[i] * pot1[i] + h1[i - 1];
    h1[i] %= mod1;
    h2[i] = second[i] * pot2[i] + h2[i - 1];
    h2[i] %= mod2;
  }
  long long ans = 0;
  for (long long i = 1; i <= n; ++i) {
    if (solve(i)) ++ans;
  }
  cout << ans << '\n';
}

```