String Subsequences

You are given strings s1 and s2, where s1 has length exactly 3. Count the ways to choose three strictly increasing indices i<j<k in s2 such that s2[i], s2[j], s2[k] equal the three characters of s1 in order. The characters do not need to be contiguous; different index choices are counted separately, even if they give the same characters. Output the exact integer without taking a modulus. The original starter declares int, but the full range overflows 32 bits; the Java/C++ solutions from the same fixed source use 64 bits. This site keeps the full range and explicitly requires exact integer output.

输入格式

The first line contains s1, of length exactly 3. The second line contains s2, with 1≤|s2|≤500000. Both lines contain only uppercase English letters A to Z, and repeated characters are allowed.

输出格式

Output the exact non-negative decimal number of ways, without a modulus or truncation. The result can be as large as 20833208333500000, which requires a 64-bit integer; floating-point approximations must not be used.

样例 1

输入：

HRW
HERHRWS

输出：

3

样例 2

输入：

ELO
HELLOWORLD

输出：

4

样例 3

输入：

ABC
ABCBABC

输出：

5

样例说明

All three public examples come from the original problem. HRW in HERHRWS matches the 1-based indices (1,3,6), (1,5,6), (4,5,6), for 3 ways; ELO in HELLOWORLD has 4 ways; ABC in ABCBABC has 5 ways.