#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
char s[maxn], t[maxn];
int pr1, mod1, pr2, mod2;
const int prs[60] = {
    73,  79,  83,  89,  97,  101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
    151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
    233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
    317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409};
const int mods[100] = {
    998244521, 998244523, 998244529, 998244601, 998244617, 998244619, 998244631,
    998244649, 998244673, 998244677, 998244679, 998244707, 998244713, 998244749,
    998244761, 998244787, 998244799, 998244803, 998244839, 998244853, 998244889,
    998244893, 998244899, 998244911, 998244943, 998244967, 998244991, 998245037,
    998245063, 998245091, 998245097, 998245099, 998245109, 998245111, 998245141,
    998245147, 998245153, 998245159, 998245169, 998245177, 998245189, 998245207,
    998245211, 998245223, 998245247, 998245331, 998245349, 998245373, 998245403,
    998245463, 998245481, 998245483, 998245487, 998245489, 998245531, 998245543,
    998245553, 998245571, 998245613, 998245631, 998245639, 998245687, 998245697,
    998245709, 998245711, 998245733, 998245739, 998245757, 998245777, 998245799,
    998245837, 998245867, 998245877, 998245909, 998245943, 998245949, 998245981,
    998246021, 998246047, 998246071, 998246077, 998246101, 998246129, 998246143,
    998246177, 998246189, 998246191, 998246237, 998246251, 998246257, 998246261,
    998246267, 998246279, 998246317, 998246363, 998246369, 998246371, 998246387,
    998246399, 998246401};
int ht1[maxn], pw1[maxn], ht2[maxn], pw2[maxn];
vector<int> pos[2];
int hash_1(int l, int r) {
  if (l == 0) return ht1[r];
  return (ht1[r] - pw1[r - l + 1] * 1ll * ht1[l - 1] % mod1 + mod1) % mod1;
}
int hash_2(int l, int r) {
  if (l == 0) return ht2[r];
  return (ht2[r] - pw2[r - l + 1] * 1ll * ht2[l - 1] % mod2 + mod2) % mod2;
}
int main() {
  srand(time(0) + clock());
  pr1 = prs[rand() % 60], mod1 = mods[rand() % 100];
  pr2 = prs[rand() % 60], mod2 = mods[rand() % 100];
  scanf("%s", s);
  scanf("%s", t);
  int n = strlen(s), m = strlen(t), c0 = 0, c1 = 0;
  if (s[0] == '1') {
    for (int i = 0; i < n; ++i) {
      if (s[i] == '0')
        s[i] = '1';
      else
        s[i] = '0';
    }
  }
  for (int i = 0; i < n; ++i) {
    if (s[i] == '0') ++c0;
    if (s[i] == '1') ++c1;
    pos[s[i] - '0'].push_back(i);
  }
  if (pos[0].size() == 0 || pos[1].size() == 0) {
    puts("0");
    return 0;
  }
  ht1[0] = ht2[0] = t[0];
  for (int i = 1; i < m; ++i) {
    ht1[i] = (1ll * ht1[i - 1] * pr1 + t[i]) % mod1;
    ht2[i] = (1ll * ht2[i - 1] * pr2 + t[i]) % mod2;
  }
  int ans = 0;
  pw1[0] = pw2[0] = 1;
  for (int i = 1; i < maxn; ++i) {
    pw1[i] = pw1[i - 1] * 1ll * pr1 % mod1;
    pw2[i] = pw2[i - 1] * 1ll * pr2 % mod2;
  }
  for (int x = 1; x * c0 < m; ++x) {
    if ((m - x * c0) % c1 != 0) continue;
    int y = (m - x * c0) / c1;
    int hx1 = hash_1(0, x - 1);
    int hy1 = hash_1(pos[1][0] * x, pos[1][0] * x + y - 1);
    int hx2 = hash_2(0, x - 1);
    int hy2 = hash_2(pos[1][0] * x, pos[1][0] * x + y - 1);
    int real_1 = 0, real_2 = 0;
    if (hx1 == hy1 && hx2 == hy2) continue;
    for (int j = 0; j < n; ++j) {
      if (s[j] == '0') {
        real_1 = (real_1 * 1ll * pw1[x] + hx1) % mod1;
        real_2 = (real_2 * 1ll * pw2[x] + hx2) % mod2;
      } else {
        real_1 = (real_1 * 1ll * pw1[y] + hy1) % mod1;
        real_2 = (real_2 * 1ll * pw2[y] + hy2) % mod2;
      }
    }
    if (real_1 == ht1[m - 1] && real_2 == ht2[m - 1]) ++ans;
  }
  printf("%d\n", ans);
  return 0;
}

### 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>
using namespace std;
const int maxn = 1e6 + 5;
char s[maxn], t[maxn];
int pr1, mod1, pr2, mod2;
const int prs[60] = {
    73,  79,  83,  89,  97,  101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
    151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
    233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
    317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409};
const int mods[100] = {
    998244521, 998244523, 998244529, 998244601, 998244617, 998244619, 998244631,
    998244649, 998244673, 998244677, 998244679, 998244707, 998244713, 998244749,
    998244761, 998244787, 998244799, 998244803, 998244839, 998244853, 998244889,
    998244893, 998244899, 998244911, 998244943, 998244967, 998244991, 998245037,
    998245063, 998245091, 998245097, 998245099, 998245109, 998245111, 998245141,
    998245147, 998245153, 998245159, 998245169, 998245177, 998245189, 998245207,
    998245211, 998245223, 998245247, 998245331, 998245349, 998245373, 998245403,
    998245463, 998245481, 998245483, 998245487, 998245489, 998245531, 998245543,
    998245553, 998245571, 998245613, 998245631, 998245639, 998245687, 998245697,
    998245709, 998245711, 998245733, 998245739, 998245757, 998245777, 998245799,
    998245837, 998245867, 998245877, 998245909, 998245943, 998245949, 998245981,
    998246021, 998246047, 998246071, 998246077, 998246101, 998246129, 998246143,
    998246177, 998246189, 998246191, 998246237, 998246251, 998246257, 998246261,
    998246267, 998246279, 998246317, 998246363, 998246369, 998246371, 998246387,
    998246399, 998246401};
int ht1[maxn], pw1[maxn], ht2[maxn], pw2[maxn];
vector<int> pos[2];
int hash_1(int l, int r) {
  if (l == 0) return ht1[r];
  return (ht1[r] - pw1[r - l + 1] * 1ll * ht1[l - 1] % mod1 + mod1) % mod1;
}
int hash_2(int l, int r) {
  if (l == 0) return ht2[r];
  return (ht2[r] - pw2[r - l + 1] * 1ll * ht2[l - 1] % mod2 + mod2) % mod2;
}
int main() {
  srand(time(0) + clock());
  pr1 = prs[rand() % 60], mod1 = mods[rand() % 100];
  pr2 = prs[rand() % 60], mod2 = mods[rand() % 100];
  scanf("%s", s);
  scanf("%s", t);
  int n = strlen(s), m = strlen(t), c0 = 0, c1 = 0;
  if (s[0] == '1') {
    for (int i = 0; i < n; ++i) {
      if (s[i] == '0')
        s[i] = '1';
      else
        s[i] = '0';
    }
  }
  for (int i = 0; i < n; ++i) {
    if (s[i] == '0') ++c0;
    if (s[i] == '1') ++c1;
    pos[s[i] - '0'].push_back(i);
  }
  if (pos[0].size() == 0 || pos[1].size() == 0) {
    puts("0");
    return 0;
  }
  ht1[0] = ht2[0] = t[0];
  for (int i = 1; i < m; ++i) {
    ht1[i] = (1ll * ht1[i - 1] * pr1 + t[i]) % mod1;
    ht2[i] = (1ll * ht2[i - 1] * pr2 + t[i]) % mod2;
  }
  int ans = 0;
  pw1[0] = pw2[0] = 1;
  for (int i = 1; i < maxn; ++i) {
    pw1[i] = pw1[i - 1] * 1ll * pr1 % mod1;
    pw2[i] = pw2[i - 1] * 1ll * pr2 % mod2;
  }
  for (int x = 1; x * c0 < m; ++x) {
    if ((m - x * c0) % c1 != 0) continue;
    int y = (m - x * c0) / c1;
    int hx1 = hash_1(0, x - 1);
    int hy1 = hash_1(pos[1][0] * x, pos[1][0] * x + y - 1);
    int hx2 = hash_2(0, x - 1);
    int hy2 = hash_2(pos[1][0] * x, pos[1][0] * x + y - 1);
    int real_1 = 0, real_2 = 0;
    if (hx1 == hy1 && hx2 == hy2) continue;
    for (int j = 0; j < n; ++j) {
      if (s[j] == '0') {
        real_1 = (real_1 * 1ll * pw1[x] + hx1) % mod1;
        real_2 = (real_2 * 1ll * pw2[x] + hx2) % mod2;
      } else {
        real_1 = (real_1 * 1ll * pw1[y] + hy1) % mod1;
        real_2 = (real_2 * 1ll * pw2[y] + hy2) % mod2;
      }
    }
    if (real_1 == ht1[m - 1] && real_2 == ht2[m - 1]) ++ans;
  }
  printf("%d\n", ans);
  return 0;
}

```