#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
ll mypow(ll b, ll n) {
  if (n == 0) return 1;
  if (n == 1) return b % MOD;
  return n % 2 == 0 ? mypow(b * b % MOD, n / 2) : mypow(b, n - 1) * b % MOD;
}
class RollingHash {
 public:
  RollingHash(string S, ll _base = 1009, ll _mod = 1e9 + 7)
      : base(_base), mod(_mod), len(S.length()) {
    hash.resize(len + 1);
    bpow.resize(len + 1);
    hash[0] = 0;
    bpow[0] = 1;
    for (int i = 0; i < len; ++i) {
      hash[i + 1] = (hash[i] * base + S[i]) % mod;
      bpow[i + 1] = bpow[i] * base % mod;
    }
  }
  ll seghash(int b, int e) {
    return (hash[e] - hash[b] * bpow[e - b] % mod + mod) % mod;
  }
  vector<ll> hash, bpow;
  ll base, mod;
  int len;
};
int main() {
  string S, T;
  cin >> S >> T;
  int N = S.length(), M = T.length();
  RollingHash rh(T);
  if (S[0] == '1') {
    for (int i = 0; i < N; ++i) {
      S[i] = '0' + '1' - S[i];
    }
  }
  int ob = -1, cnt[2] = {0, 0};
  for (int i = 0; i < N; ++i) {
    if (S[i] == '1' && ob < 0) ob = i;
    ++cnt[S[i] - '0'];
  }
  int ans = 0;
  for (int z = 1; z < M; ++z) {
    if (cnt[0] * z >= M) break;
    if ((M - cnt[0] * z) % cnt[1] > 0) continue;
    int o = (M - cnt[0] * z) / cnt[1];
    ll zh = rh.seghash(0, z);
    ll oh = rh.seghash(z * ob, z * ob + o);
    if (zh == oh) continue;
    ll H = 0;
    for (char c : S) {
      if (c == '0') {
        H = (H * mypow(1009LL, z) + zh) % MOD;
      } else {
        H = (H * mypow(1009LL, o) + oh) % MOD;
      }
    }
    if (H == rh.seghash(0, M)) ++ans;
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Your task is to create 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;
using ll = long long;
const ll MOD = 1e9 + 7;
ll mypow(ll b, ll n) {
  if (n == 0) return 1;
  if (n == 1) return b % MOD;
  return n % 2 == 0 ? mypow(b * b % MOD, n / 2) : mypow(b, n - 1) * b % MOD;
}
class RollingHash {
 public:
  RollingHash(string S, ll _base = 1009, ll _mod = 1e9 + 7)
      : base(_base), mod(_mod), len(S.length()) {
    hash.resize(len + 1);
    bpow.resize(len + 1);
    hash[0] = 0;
    bpow[0] = 1;
    for (int i = 0; i < len; ++i) {
      hash[i + 1] = (hash[i] * base + S[i]) % mod;
      bpow[i + 1] = bpow[i] * base % mod;
    }
  }
  ll seghash(int b, int e) {
    return (hash[e] - hash[b] * bpow[e - b] % mod + mod) % mod;
  }
  vector<ll> hash, bpow;
  ll base, mod;
  int len;
};
int main() {
  string S, T;
  cin >> S >> T;
  int N = S.length(), M = T.length();
  RollingHash rh(T);
  if (S[0] == '1') {
    for (int i = 0; i < N; ++i) {
      S[i] = '0' + '1' - S[i];
    }
  }
  int ob = -1, cnt[2] = {0, 0};
  for (int i = 0; i < N; ++i) {
    if (S[i] == '1' && ob < 0) ob = i;
    ++cnt[S[i] - '0'];
  }
  int ans = 0;
  for (int z = 1; z < M; ++z) {
    if (cnt[0] * z >= M) break;
    if ((M - cnt[0] * z) % cnt[1] > 0) continue;
    int o = (M - cnt[0] * z) / cnt[1];
    ll zh = rh.seghash(0, z);
    ll oh = rh.seghash(z * ob, z * ob + o);
    if (zh == oh) continue;
    ll H = 0;
    for (char c : S) {
      if (c == '0') {
        H = (H * mypow(1009LL, z) + zh) % MOD;
      } else {
        H = (H * mypow(1009LL, o) + oh) % MOD;
      }
    }
    if (H == rh.seghash(0, M)) ++ans;
  }
  cout << ans << endl;
  return 0;
}

```