Problem Brief

String Subsequences 🐳

INTERNOA

Given two strings, determine the number of times the first one appears as a subsequence in the second one. A subsequence is created by eliminating any number of characters from a string (possibly 0) without changing the order of the characters retained.

Function Description

Complete the function getSubsequenceCount in the editor below.

getSubsequenceCount has the following parameters:

string s1: the first string, which always has a length of 3

string s2: the second string

Returns

int: the number of times s1 appears as a subsequence in s2

1Example 1

Input

s1 = "HRW", s2 = "HERHRWS"

Output

Explanation

"HRW" appears as a subsequence in "HERHRWS" 3 times at positions (1, 3, 6), (1, 5, 6), and (4, 5, 6). Therefore, the answer is 3.

2Example 2

Input

s1 = "ELO", s2 = "HELLOWORLD"

Output

Explanation

"ELO" appears as a subsequence in "HELLOWORLD" 4 times at positions (2, 3, 5), (2, 3, 7), (2, 4, 5), and (2, 4, 7). Therefore, the answer is 4.

3Example 3

Input

s1 = "ABC", s2 = "ABCBABC"

Output

Explanation

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, 6, 7) and (5, 6, 7). So, the answer turns out to be 🖐️.

Constraints

Limits and guarantees your solution can rely on.

length of s1 = 3

1 ≤ length of s2 ≤ 5*10⁵

s1 and s2 consist of uppercase English letters, A-Z.