Typewriter Mishap

Violet's typewriter has been overused and its keys are wearing out. Sometimes when she types a key, it fails to register. Since Violet types blindly, she never notices these occasional failures. One day, she continues writing an unfinished letter on this faulty machine.

You are given the already written part of the letter and a sequence of operations that Violet intends to perform. There are two kinds of operations:

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

The backspace is represented by the lowercase letter \(u\) in the operations, and it deletes the last character of the current letter if it exists. (If the letter is empty, the backspace operation does nothing.)

Violet will press the keys sequentially. For each key press (either an uppercase letter or a backspace), it might not register (that is, the operation might be ineffective). In other words, for each intended operation, there is an independent choice: it either takes effect or it is ignored.

After processing all operations (with each key press independently effective or not), some final letter is produced. Note that the empty letter is also considered a result.

Your task is to determine how many distinct final letters can be produced. Since the number can be very large, output the answer modulo \(19260817\) (note that \(19260817 = 0x125E591\) in hexadecimal).

Note on the simulation: The process starts with the initial letter. Then, for each operation in the given order:

• If the operation is an uppercase letter, either append it to the current letter (if effective) or do nothing (if ignored).
• If the operation is \(u\) (backspace), then if effective, remove the last character of the current letter if it exists; if the letter is empty or the operation is ignored, nothing happens.

inputFormat

The input consists of two lines:

1. The first line is a string representing the part of the letter that has already been written. It may be empty.
2. The second line is a string representing the sequence of operations Violet intends to perform. Each character is either an uppercase letter (denoting an insertion) or the lowercase letter u (denoting a backspace).

outputFormat

Output a single integer: the number of distinct final letters that can be produced, taken modulo \(19260817\).

sample

1