#include <bits/stdc++.h>
using namespace std;
template <class T>
void _R(T &x) {
  cin >> x;
}
void _R(int &x) { scanf("%d", &x); }
void _R(long long &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &...tail) {
  _R(head);
  R(tail...);
}
template <class T>
void _W(const T &x) {
  cout << x;
}
void _W(const int &x) { printf("%d", x); }
void _W(const long long &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T, class U>
void _W(const pair<T, U> &x) {
  _W(x.first);
  putchar(' ');
  _W(x.second);
}
template <class T>
void _W(const vector<T> &x) {
  for (auto i = x.begin(); i != x.end(); _W(*i++))
    if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &...tail) {
  _W(head);
  putchar(sizeof...(tail) ? ' ' : '\n');
  W(tail...);
}
int MOD = 1e9 + 7;
void ADD(long long &x, long long v) {
  x = (x + v) % MOD;
  if (x < 0) x += MOD;
}
const int SIZE = 1e6 + 10;
const int MUL = 131;
bool PRE_DONE = 0;
int mul[SIZE], inv[SIZE];
long long mypow(long long x, long long y) {
  x %= MOD;
  long long res = 1 % MOD;
  while (y) {
    if (y & 1) res = res * x % MOD;
    y >>= 1;
    x = x * x % MOD;
  }
  return res;
}
void pre_do() {
  if (PRE_DONE) return;
  PRE_DONE = 1;
  mul[0] = 1;
  for (int i = (1); i < (SIZE); ++i) {
    mul[i] = (long long)mul[i - 1] * MUL % MOD;
  }
  long long tmp = mypow(MUL, MOD - 2);
  inv[0] = 1;
  for (int i = (1); i < (SIZE); ++i) inv[i] = inv[i - 1] * tmp % MOD;
}
struct string_hash {
  vector<int> dp;
  void build(string _s) {
    pre_do();
    dp = vector<int>(((int)(_s).size()) + 1);
    for (int i = 0; i < (((int)(_s).size())); ++i) {
      dp[i + 1] = (dp[i] + (long long)mul[i] * _s[i]) % MOD;
    }
  }
  int get(int L, int R) {
    if (L > R) return 0;
    R++;
    long long v = (long long)(dp[R] - dp[L]) * inv[L] % MOD;
    if (v < 0) v += MOD;
    return v;
  }
};
int main() {
  string s1, s2;
  R(s1, s2);
  int cnt[2] = {};
  for (int i = 0; i < (((int)(s1).size())); ++i) {
    cnt[s1[i] - '0']++;
  }
  string_hash hh;
  int an = 0;
  hh.build(s2);
  for (int i = 1; i * cnt[0] < ((int)(s2).size()); i++) {
    if ((((int)(s2).size()) - cnt[0] * i) % cnt[1]) continue;
    int j = (((int)(s2).size()) - cnt[0] * i) / cnt[1];
    int v[2] = {-1, -1};
    int now = 0;
    bool err = 0;
    for (int k = 0; k < (((int)(s1).size())); ++k) {
      if (s1[k] == '0') {
        if (v[0] == -1) {
          v[0] = hh.get(now, now + i - 1);
        } else {
          if (v[0] != hh.get(now, now + i - 1)) err = 1;
        }
        now += i;
      } else {
        if (v[1] == -1) {
          v[1] = hh.get(now, now + j - 1);
        } else {
          if (v[1] != hh.get(now, now + j - 1)) err = 1;
        }
        now += j;
      }
      if (err) break;
    }
    if (v[0] == v[1] && i == j) err = 1;
    if (!err) an++;
  }
  W(an);
  return 0;
}

### Prompt

Generate 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>
using namespace std;
template <class T>
void _R(T &x) {
  cin >> x;
}
void _R(int &x) { scanf("%d", &x); }
void _R(long long &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template <class T, class... U>
void R(T &head, U &...tail) {
  _R(head);
  R(tail...);
}
template <class T>
void _W(const T &x) {
  cout << x;
}
void _W(const int &x) { printf("%d", x); }
void _W(const long long &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template <class T, class U>
void _W(const pair<T, U> &x) {
  _W(x.first);
  putchar(' ');
  _W(x.second);
}
template <class T>
void _W(const vector<T> &x) {
  for (auto i = x.begin(); i != x.end(); _W(*i++))
    if (i != x.cbegin()) putchar(' ');
}
void W() {}
template <class T, class... U>
void W(const T &head, const U &...tail) {
  _W(head);
  putchar(sizeof...(tail) ? ' ' : '\n');
  W(tail...);
}
int MOD = 1e9 + 7;
void ADD(long long &x, long long v) {
  x = (x + v) % MOD;
  if (x < 0) x += MOD;
}
const int SIZE = 1e6 + 10;
const int MUL = 131;
bool PRE_DONE = 0;
int mul[SIZE], inv[SIZE];
long long mypow(long long x, long long y) {
  x %= MOD;
  long long res = 1 % MOD;
  while (y) {
    if (y & 1) res = res * x % MOD;
    y >>= 1;
    x = x * x % MOD;
  }
  return res;
}
void pre_do() {
  if (PRE_DONE) return;
  PRE_DONE = 1;
  mul[0] = 1;
  for (int i = (1); i < (SIZE); ++i) {
    mul[i] = (long long)mul[i - 1] * MUL % MOD;
  }
  long long tmp = mypow(MUL, MOD - 2);
  inv[0] = 1;
  for (int i = (1); i < (SIZE); ++i) inv[i] = inv[i - 1] * tmp % MOD;
}
struct string_hash {
  vector<int> dp;
  void build(string _s) {
    pre_do();
    dp = vector<int>(((int)(_s).size()) + 1);
    for (int i = 0; i < (((int)(_s).size())); ++i) {
      dp[i + 1] = (dp[i] + (long long)mul[i] * _s[i]) % MOD;
    }
  }
  int get(int L, int R) {
    if (L > R) return 0;
    R++;
    long long v = (long long)(dp[R] - dp[L]) * inv[L] % MOD;
    if (v < 0) v += MOD;
    return v;
  }
};
int main() {
  string s1, s2;
  R(s1, s2);
  int cnt[2] = {};
  for (int i = 0; i < (((int)(s1).size())); ++i) {
    cnt[s1[i] - '0']++;
  }
  string_hash hh;
  int an = 0;
  hh.build(s2);
  for (int i = 1; i * cnt[0] < ((int)(s2).size()); i++) {
    if ((((int)(s2).size()) - cnt[0] * i) % cnt[1]) continue;
    int j = (((int)(s2).size()) - cnt[0] * i) / cnt[1];
    int v[2] = {-1, -1};
    int now = 0;
    bool err = 0;
    for (int k = 0; k < (((int)(s1).size())); ++k) {
      if (s1[k] == '0') {
        if (v[0] == -1) {
          v[0] = hh.get(now, now + i - 1);
        } else {
          if (v[0] != hh.get(now, now + i - 1)) err = 1;
        }
        now += i;
      } else {
        if (v[1] == -1) {
          v[1] = hh.get(now, now + j - 1);
        } else {
          if (v[1] != hh.get(now, now + j - 1)) err = 1;
        }
        now += j;
      }
      if (err) break;
    }
    if (v[0] == v[1] && i == j) err = 1;
    if (!err) an++;
  }
  W(an);
  return 0;
}

```