Problem Description

Given a grid with $N$ rows and $M$ columns. There are two players. They need to choose two cells as their initial positions, and the two initial positions must be different. There is also an operation sequence $S$, where each operation is one of the following four types:

• U: move up by one cell;
• D: move down by one cell;
• L: move left by one cell;
• R: move right by one cell.

The two players move simultaneously according to the operation sequence $S$. For each operation in the sequence, both players try to move one cell in the corresponding direction at the same time. If a player would move out of the grid boundary in that direction, then in this step the player stays in the original cell and does not move.

Now, you need to compute how many different pairs of initial positions can make the two players end up in the same cell after executing the entire operation sequence.

In particular, the pair of initial positions is considered an ordered pair: if the two players' initial positions are $(r_1, c_1)$ and $(r_2, c_2)$, then $((r_1, c_1), (r_2, c_2))$ and $((r_2, c_2), (r_1, c_1))$ are considered two different solutions.

Input Format

The input has two lines.

The first line contains two integers $N, M$.

The second line contains a string $S$, representing the operation sequence.

Output Format

Output one integer, representing the number of pairs of initial positions that satisfy the condition.

10 9
UULDURRRDLDLDD

284

Hint

Constraints

• For $30\%$ of the testdata, $N, M \le 50$, $|S| \le 1000$.
• For all testdata, $N, M \le 5000$, $1 \le |S| \le 10^6$.

Translated by ChatGPT 5