Background

As long as the client has the intention, no matter where they are, I can provide door-to-door service. I am the Auto Memory Doll service—Violet Evergarden.

Problem Description

Violet's typewriter has been used for too long, and the keys have started to wear out, so sometimes a key press does not respond. Violet always touch-types, so she would not notice when a key press fails. One day, she continues using this typewriter to finish a letter that is not yet complete.

You are given the already written part of the letter and the operations Violet wants to perform. There are two kinds of operations Violet may want to do:

1. Type an uppercase letter at the end of the letter.
2. Perform a backspace.

Backspace is represented by the lowercase letter $\mathrm{u}$, meaning deleting the last character of the current letter. Of course, if the letter is empty, backspace has no effect.

Violet will press the keys in the order she intends, but each time she presses a key (typing an uppercase letter or performing a backspace), it may fail to respond (i.e., this operation becomes invalid). How many different final letters are possible? (The empty letter also counts as a letter.)

You only need the result modulo 0x125E591 (hexadecimal).

Input Format

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

The second line contains a string of length $n$ representing the already written part of the letter. It is guaranteed that every character in the string is an uppercase letter.

The third line contains a string of length $m$ representing the operations Violet wants to perform. It is guaranteed that every character in the string is either an uppercase letter or $\mathrm{u}$.

Output Format

Output one integer: the answer modulo 0x125E591.

2 4
AB
AuAB

9

10 5
AABBAACBAC
ABAAC

20

1 3
U
uUu

3

Hint

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

Constraints

Sample Explanation

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

Sample 2: There are too many, omitted.

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

Translated by ChatGPT 5