Codeforces Round #416 (Div. 2) has been moved to start on 27.05.2017 09:35 (UTC). ×

D. Colorful Stones
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are two sequences of colorful stones. The color of each stone is one of red, green, or blue. You are given two strings s and t. The i-th (1-based) character of s represents the color of the i-th stone of the first sequence. Similarly, the i-th (1-based) character of t represents the color of the i-th stone of the second sequence. If the character is "R", "G", or "B", the color of the corresponding stone is red, green, or blue, respectively.

Initially Squirrel Liss is standing on the first stone of the first sequence and Cat Vasya is standing on the first stone of the second sequence. You can perform the following instructions zero or more times.

Each instruction is one of the three types: "RED", "GREEN", or "BLUE". After an instruction c, the animals standing on stones whose colors are c will move one stone forward. For example, if you perform an instruction «RED», the animals standing on red stones will move one stone forward. You are not allowed to perform instructions that lead some animals out of the sequences. In other words, if some animals are standing on the last stones, you can't perform the instructions of the colors of those stones.

A pair of positions (position of Liss, position of Vasya) is called a state. A state is called reachable if the state is reachable by performing instructions zero or more times from the initial state (1, 1). Calculate the number of distinct reachable states.

Input

The input contains two lines. The first line contains the string s (1 ≤ |s| ≤ 106). The second line contains the string t (1 ≤ |t| ≤ 106). The characters of each string will be one of "R", "G", or "B".

Output

Print the number of distinct reachable states in a single line.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples
Input
RBR
RGG
Output
5
Input
RGBB
BRRBRR
Output
19
Input
RRRRRRRRRR
RRRRRRRR
Output
8
Note

In the first example, there are five reachable states: (1, 1), (2, 2), (2, 3), (3, 2), and (3, 3). For example, the state (3, 3) is reachable because if you perform instructions "RED", "GREEN", and "BLUE" in this order from the initial state, the state will be (3, 3). The following picture shows how the instructions work in this case.