#include <bits/stdc++.h>
const double PI = acos(-1.0);
using namespace std;
int setb(int n, int pos) { return n = n | (1 << pos); }
int resb(int n, int pos) { return n = n & ~(1 << pos); }
bool checkb(int n, int pos) { return (bool)(n & (1 << pos)); }
inline long long bigmod(long long b, long long p, long long m) {
  long long ret = 1, cur = b % m;
  while (p) {
    if (p & 1) ret = (ret * cur) % m;
    cur = (cur * cur) % m;
    p = p >> 1;
  }
  return ret;
}
struct simplehash {
  int len;
  long long base, mod;
  vector<int> P, H, R;
  simplehash() {}
  simplehash(const char* str, long long b, long long m) {
    base = b, mod = m, len = strlen(str);
    P.resize(len + 3, 1), H.resize(len + 3, 0), R.resize(len + 3, 0);
    for (int i = 1; i <= len; i++) P[i] = (P[i - 1] * base) % mod;
    for (int i = 1; i <= len; i++)
      H[i] = (H[i - 1] * base + str[i - 1] + 1007) % mod;
    for (int i = len; i >= 1; i--)
      R[i] = (R[i + 1] * base + str[i - 1] + 1007) % mod;
  }
  inline int range_hash(int l, int r) {
    int hashval = H[r + 1] - ((long long)P[r - l + 1] * H[l] % mod);
    return (hashval < 0 ? hashval + mod : hashval);
  }
  inline int reverse_hash(int l, int r) {
    ;
    int hashval = R[l + 1] - ((long long)P[r - l + 1] * R[r + 2] % mod);
    return (hashval < 0 ? hashval + mod : hashval);
  }
};
struct stringhash {
  simplehash sh1, sh2;
  stringhash() {}
  stringhash(const char* str) {
    sh1 = simplehash(str, 1949313259, 2091573227);
    sh2 = simplehash(str, 1997293877, 2117566807);
  }
  inline long long range_hash(int l, int r) {
    return ((long long)sh1.range_hash(l, r) << 32) ^ sh2.range_hash(l, r);
  }
  inline long long reverse_hash(int l, int r) {
    return ((long long)sh1.reverse_hash(l, r) << 32) ^ sh2.reverse_hash(l, r);
  }
};
stringhash h;
char s[1000005], t[1000005];
int n, m;
long long single_solve(int z, int o) {
  int l = 0;
  long long zhash, ohash;
  bool zflag = false, oflag = false;
  for (int i = 0; i < n; i++) {
    int r;
    if (s[i] == '0')
      r = l + z - 1;
    else
      r = l + o - 1;
    long long val = h.range_hash(l, r);
    if (s[i] == '0') {
      if (zflag == false)
        zhash = val;
      else {
        if (zhash != val) return 0;
      }
      zflag = true;
    } else {
      if (oflag == false)
        ohash = val;
      else {
        if (ohash != val) return 0;
      }
      oflag = true;
    }
    l = r + 1;
  }
  assert(l == m);
  return zhash != ohash;
}
void solve() {
  h = stringhash(t);
  int z = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == '0') z++;
  }
  int o = n - z;
  long long ret = 0;
  for (int i = 1; i <= m; i++) {
    long long zlen = (long long)z * i;
    if (zlen >= m) break;
    long long olen = m - zlen;
    if (olen % o == 0) {
      long long my = single_solve(zlen / z, olen / o);
      ret += my;
    }
  }
  printf("%lld\n", ret);
}
int main() {
  scanf("%s", s);
  n = strlen(s);
  scanf("%s", t);
  m = strlen(t);
  solve();
  return 0;
}

### Prompt

Please provide a cpp coded solution 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>
const double PI = acos(-1.0);
using namespace std;
int setb(int n, int pos) { return n = n | (1 << pos); }
int resb(int n, int pos) { return n = n & ~(1 << pos); }
bool checkb(int n, int pos) { return (bool)(n & (1 << pos)); }
inline long long bigmod(long long b, long long p, long long m) {
  long long ret = 1, cur = b % m;
  while (p) {
    if (p & 1) ret = (ret * cur) % m;
    cur = (cur * cur) % m;
    p = p >> 1;
  }
  return ret;
}
struct simplehash {
  int len;
  long long base, mod;
  vector<int> P, H, R;
  simplehash() {}
  simplehash(const char* str, long long b, long long m) {
    base = b, mod = m, len = strlen(str);
    P.resize(len + 3, 1), H.resize(len + 3, 0), R.resize(len + 3, 0);
    for (int i = 1; i <= len; i++) P[i] = (P[i - 1] * base) % mod;
    for (int i = 1; i <= len; i++)
      H[i] = (H[i - 1] * base + str[i - 1] + 1007) % mod;
    for (int i = len; i >= 1; i--)
      R[i] = (R[i + 1] * base + str[i - 1] + 1007) % mod;
  }
  inline int range_hash(int l, int r) {
    int hashval = H[r + 1] - ((long long)P[r - l + 1] * H[l] % mod);
    return (hashval < 0 ? hashval + mod : hashval);
  }
  inline int reverse_hash(int l, int r) {
    ;
    int hashval = R[l + 1] - ((long long)P[r - l + 1] * R[r + 2] % mod);
    return (hashval < 0 ? hashval + mod : hashval);
  }
};
struct stringhash {
  simplehash sh1, sh2;
  stringhash() {}
  stringhash(const char* str) {
    sh1 = simplehash(str, 1949313259, 2091573227);
    sh2 = simplehash(str, 1997293877, 2117566807);
  }
  inline long long range_hash(int l, int r) {
    return ((long long)sh1.range_hash(l, r) << 32) ^ sh2.range_hash(l, r);
  }
  inline long long reverse_hash(int l, int r) {
    return ((long long)sh1.reverse_hash(l, r) << 32) ^ sh2.reverse_hash(l, r);
  }
};
stringhash h;
char s[1000005], t[1000005];
int n, m;
long long single_solve(int z, int o) {
  int l = 0;
  long long zhash, ohash;
  bool zflag = false, oflag = false;
  for (int i = 0; i < n; i++) {
    int r;
    if (s[i] == '0')
      r = l + z - 1;
    else
      r = l + o - 1;
    long long val = h.range_hash(l, r);
    if (s[i] == '0') {
      if (zflag == false)
        zhash = val;
      else {
        if (zhash != val) return 0;
      }
      zflag = true;
    } else {
      if (oflag == false)
        ohash = val;
      else {
        if (ohash != val) return 0;
      }
      oflag = true;
    }
    l = r + 1;
  }
  assert(l == m);
  return zhash != ohash;
}
void solve() {
  h = stringhash(t);
  int z = 0;
  for (int i = 0; i < n; i++) {
    if (s[i] == '0') z++;
  }
  int o = n - z;
  long long ret = 0;
  for (int i = 1; i <= m; i++) {
    long long zlen = (long long)z * i;
    if (zlen >= m) break;
    long long olen = m - zlen;
    if (olen % o == 0) {
      long long my = single_solve(zlen / z, olen / o);
      ret += my;
    }
  }
  printf("%lld\n", ret);
}
int main() {
  scanf("%s", s);
  n = strlen(s);
  scanf("%s", t);
  m = strlen(t);
  solve();
  return 0;
}

```