Mail.Ru Cup 2018 Round 3 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

data structures

hashing

strings

*2100

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Check Transcription

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOne 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 \le |s| \le 10^5$$$) consisting of zeros and ones — the original signal.

The second line contains a string $$$t$$$ ($$$1 \le |t| \le 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"

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/28/2024 13:33:12 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|