Given two strings, find out how many times the first string appears as a subsequence within the second string. A subsequence is formed by removing any number of characters (including zero) from a string without altering the order of the remaining characters.

Problem

Given two strings, find out how many times the first string appears as a subsequence within the second string.

Example 1:

s1 = "ABC" s2 = "ABCBA"

The string s1 appears 5 times as a subsequence in s2 at 1-indexed positions of {1, 2, 3}, {1, 2, 7}, {1, 4, 7}, {1, 5, 6, 7}, and {5, 6, 7}. The answer is 5.

Example 2:

s1 = "HRW" s2 = "HERHRWS"

The string s1 appears 3 times as a subsequence in s2.

Example 3:

s1 = "ELO" s2 = "HELLO WORLD"

The string s1 appears 4 times as a subsequence in s2.

Input

Two strings s1 and s2.

Output

The number of times s1 appears as a subsequence in s2.

Constraints

• length of s1 = 3
• 1 ≤ length of s2 ≤ 5*10^5
• s1 and s2 consist of uppercase English letters, A-Z.