#include <bits/stdc++.h>
using namespace std;
mt19937 rng(time(NULL));
long long ran(long long l, long long r) { return rng() % (r - l + 1) + l; }
bool is_prime(long long x) {
  for (long long i = 2; i * i <= x; i++)
    if (x % i == 0) return 0;
  return 1;
}
const long long maxM = 1e6 + 69;
const long long K = 269;
const long long MS = 3;
long long MODS[MS];
long long MM[MS];
using hsh = array<long long, MS>;
hsh powK[maxM];
hsh operator+(hsh h, long long c) {
  for (long long i = 0; i < MS; i++) h[i] = (h[i] * K + c) % MODS[i];
  return h;
}
void init_hsh() {
  static const long long MIN = 1e9, MAX = 2e9;
  for (long long i = 0; i < MS; i++) {
    MODS[i] = ran(MIN, MAX);
    while (!is_prime(MODS[i])) MODS[i]++;
    MM[i] = MODS[i] * MODS[i];
  }
  for (long long i = 0; i < MS; i++) powK[0][i] = 1;
  for (long long i = 1; i < maxM; i++) powK[i] = powK[i - 1] + 0;
}
struct str {
  vector<hsh> val;
  void init(const string& s) {
    val.resize(s.size());
    for (long long i = 1; i < s.size(); i++) val[i] = val[i - 1] + s[i];
  }
  hsh calc(long long l, long long r) {
    hsh res;
    for (long long i = 0; i < MS; i++)
      res[i] =
          (val[r][i] - val[l - 1][i] * powK[r - l + 1][i] + MM[i]) % MODS[i];
    return res;
  }
};
long long n, m;
string s, t;
str ht;
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  init_hsh();
  cin >> s >> t;
  n = s.size();
  m = t.size();
  s = ' ' + s;
  t = ' ' + t;
  ht.init(t);
  long long cnt0 = 0, cnt1 = 0;
  for (char& c : s) {
    if (c == '0')
      cnt0++;
    else if (c == '1')
      cnt1++;
  }
  long long ans = 0;
  for (long long len0 = 1; len0 <= m; len0++) {
    long long remains = m - len0 * cnt0;
    if (remains <= 0 || remains % cnt1 != 0) continue;
    long long len1 = remains / cnt1;
    long long cur = 1;
    hsh val0, val1;
    val0[0] = -1;
    val1[0] = -1;
    for (long long i = 1; i <= n; i++) {
      if (s[i] == '0') {
        hsh val = ht.calc(cur, cur + len0 - 1);
        if (val0[0] == -1) val0 = val;
        if (val != val0) goto flag;
        cur += len0;
      } else {
        hsh val = ht.calc(cur, cur + len1 - 1);
        if (val1[0] == -1) val1 = val;
        if (val != val1) goto flag;
        cur += len1;
      }
      if (val0[0] != -1 && val1[0] != -1 && val0 == val1) goto flag;
    }
    assert(cur == m + 1);
    ans++;
  flag:;
  }
  cout << ans;
}

### Prompt

Your challenge is to write 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;
mt19937 rng(time(NULL));
long long ran(long long l, long long r) { return rng() % (r - l + 1) + l; }
bool is_prime(long long x) {
  for (long long i = 2; i * i <= x; i++)
    if (x % i == 0) return 0;
  return 1;
}
const long long maxM = 1e6 + 69;
const long long K = 269;
const long long MS = 3;
long long MODS[MS];
long long MM[MS];
using hsh = array<long long, MS>;
hsh powK[maxM];
hsh operator+(hsh h, long long c) {
  for (long long i = 0; i < MS; i++) h[i] = (h[i] * K + c) % MODS[i];
  return h;
}
void init_hsh() {
  static const long long MIN = 1e9, MAX = 2e9;
  for (long long i = 0; i < MS; i++) {
    MODS[i] = ran(MIN, MAX);
    while (!is_prime(MODS[i])) MODS[i]++;
    MM[i] = MODS[i] * MODS[i];
  }
  for (long long i = 0; i < MS; i++) powK[0][i] = 1;
  for (long long i = 1; i < maxM; i++) powK[i] = powK[i - 1] + 0;
}
struct str {
  vector<hsh> val;
  void init(const string& s) {
    val.resize(s.size());
    for (long long i = 1; i < s.size(); i++) val[i] = val[i - 1] + s[i];
  }
  hsh calc(long long l, long long r) {
    hsh res;
    for (long long i = 0; i < MS; i++)
      res[i] =
          (val[r][i] - val[l - 1][i] * powK[r - l + 1][i] + MM[i]) % MODS[i];
    return res;
  }
};
long long n, m;
string s, t;
str ht;
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  init_hsh();
  cin >> s >> t;
  n = s.size();
  m = t.size();
  s = ' ' + s;
  t = ' ' + t;
  ht.init(t);
  long long cnt0 = 0, cnt1 = 0;
  for (char& c : s) {
    if (c == '0')
      cnt0++;
    else if (c == '1')
      cnt1++;
  }
  long long ans = 0;
  for (long long len0 = 1; len0 <= m; len0++) {
    long long remains = m - len0 * cnt0;
    if (remains <= 0 || remains % cnt1 != 0) continue;
    long long len1 = remains / cnt1;
    long long cur = 1;
    hsh val0, val1;
    val0[0] = -1;
    val1[0] = -1;
    for (long long i = 1; i <= n; i++) {
      if (s[i] == '0') {
        hsh val = ht.calc(cur, cur + len0 - 1);
        if (val0[0] == -1) val0 = val;
        if (val != val0) goto flag;
        cur += len0;
      } else {
        hsh val = ht.calc(cur, cur + len1 - 1);
        if (val1[0] == -1) val1 = val;
        if (val != val1) goto flag;
        cur += len1;
      }
      if (val0[0] != -1 && val1[0] != -1 && val0 == val1) goto flag;
    }
    assert(cur == m + 1);
    ans++;
  flag:;
  }
  cout << ans;
}

```