Problem Background

As long as the client has the intention, no matter where they are, we can provide上门服务. I am an automatic手记人偶 service - Violet Evergarden.

Problem Description

Violet's typewriter is old and the keys are starting to wear out, so sometimes the keys don't respond. Violet is a touch typist, so she doesn't notice when a key doesn't respond. One day, she continues to complete a letter that hasn't been finished yet using this typewriter.

You are given the part of the letter that has already been written and the operations Violet wants to perform. There are two types of operations she wants to perform:
1. Input a capital letter at the end of the letter.
2. Perform a backspace.

A backspace is represented by the lowercase letter $\mathrm{u}$, which deletes the last character in the current letter. Of course, backspacing has no effect when the letter is empty.

Violet will press the keys she wants to press in order, and each time she presses a key (inputting a capital letter or performing a backspace), there is a possibility that it won't respond (i.e., the operation is invalid). How many possible outcomes are there for the final letter? (An empty letter is also considered a letter)

Violet only wants to know the result modulo 0x125E591 (hexadecimal).

Input Format

The first line contains two positive integers $n$ and $m$, representing the length of the already written letter and the number of operations Violet wants to perform (number of characters + number of backspaces), respectively.

The second line is a string of length $n$ representing the already written letter, ensuring that each character in the string is a capital letter.

The third line is a string of length $m$ representing the operations Violet wants to perform, ensuring that each character in the string is either a capital letter or $\mathrm{u}$.

Output Format

An integer representing the answer modulo 0x125E591.

Sample Input and Output

Sample Input #1

2 4
AB
AuAB

Sample Output #1

9

Sample Input #2

10 5
AABBAACBAC
ABAAC

Sample Output #2

20

Sample Input #3

1 3
U
uUu

Sample Output #3

3

Notes

$1 \le n, m \le 5 \times 10^6$

Sample Explanation

Sample 1: The 9 possible letters are: A, AA, AB, AAB, ABA, ABB, ABAA, ABAB, ABAAB.

Sample 2: Too many to list.

Sample 3: The 3 possible letters are: empty, U, UU.

见题面 Input 部分

见题面 Output 部分