Counting Similar Substrings

In this problem, you are given two non-empty sequences A and B consisting of digits. A substring of A is defined as any contiguous segment of A. We say that two sequences are similar if when each is compressed into groups of consecutive identical characters, the resulting sequences have the same length, the same characters in order, and the counts of each group differ by a common positive factor.

More formally, suppose a sequence \( \Alpha \) is written as \[ \underbrace{AA\ldots A}_{a_1}\,\underbrace{BB\ldots B}_{a_2}\,\underbrace{CC\ldots C}_{a_3}\,\ldots \] and another sequence \( \Beta \) is written as \[ \underbrace{AA\ldots A}_{b_1}\,\underbrace{BB\ldots B}_{b_2}\,\underbrace{CC\ldots C}_{b_3}\,\ldots \] where the letters and counts are positive integers. We say \( \Alpha \) and \( \Beta \) are similar if there exists a positive real number \( k > 0 \) such that \[ \frac{a_1}{b_1} = \frac{a_2}{b_2} = \frac{a_3}{b_3} = \cdots = k. \] Note that the empty sequence is not similar to any sequence. It can be proved that this similarity relation is transitive.

For instance:

• 112244 and 111222444 are similar since their run length encodings are [('1',2),('2',2),('4',2)] and [('1',3),('2',3),('4',3)] respectively, and for each group \(k = \frac{2}{3}\) (or equivalently, \(\frac{3}{?}\)) holds.
• 111333 and 13 are similar.
• 226 and 226 are similar.
• 33889 and 33388899 are not similar.

When a given strike sequence (here, a substring of A) has multiple ways to cause effective strikes (i.e. multiple substrings are similar to the standard sequence B), then each occurrence counts. For example:

• When A = 11 and B = 1, the substrings 1 (first position), 1 (second position) and 11 are all similar to B, totalling 3 effective strikes.
• When A = 6666 and B = 66, all substrings of A (of which there are 10) are similar to B.

Your task is: Given sequences A and B, count how many substrings of A are similar to B.

inputFormat

The input consists of two lines. The first line contains the string A, and the second line contains the string B. Both A and B consist only of digits and are non-empty.

outputFormat

Output a single integer: the number of substrings of A that are similar to B.

sample

11
1

3