Check Transcription
Description
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$.
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'.
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$.
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$.
Samples
01
aaaaaa
4
001
kokokokotlin
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"