Question
Subsequence Pattern Matching
You are given a string consisting only of characters KaTeX can only parse string typed expression and KaTeX can only parse string typed expression. Your task is to count the number of subsequences equal to the string "abba".
A subsequence is a sequence that can be derived from the string by deleting some or no characters without changing the order of the remaining characters.
Since the answer can be large, print it modulo KaTeX can only parse string typed expression.
Input
The first line contains a single integer KaTeX can only parse string typed expression — the length of the string.
The second line contains a string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression, consisting only of characters KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.
The second line contains a string KaTeX can only parse string typed expression of length KaTeX can only parse string typed expression, consisting only of characters KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.
Output
Print a single integer — the number of subsequences equal to KaTeX can only parse string typed expression modulo KaTeX can only parse string typed expression.
Example
Input
6
abbaba
Output
4
Explanation
Valid subsequences forming "abba":
(0, 1, 2, 3) → a b b a
(0, 1, 2, 5) → a b b a
(0, 1, 4, 5) → a b b a
(0, 2, 4, 5) → a b b a
Total = 4 subsequences.
6
abbaba
Output
4
Explanation
Valid subsequences forming "abba":
(0, 1, 2, 3) → a b b a
(0, 1, 2, 5) → a b b a
(0, 1, 4, 5) → a b b a
(0, 2, 4, 5) → a b b a
Total = 4 subsequences.