Programmable Snake

Konia makes budget mobile devices, and its market share has been falling lately. To save the company, the board decided to change the most famous game on every Konia device, Snake. Yes, again.

The game is played on a grid of H rows and W columns. Rows are numbered from 1 to H from top to bottom, and columns are numbered from 1 to W from left to right. Cell A is written as $(A_r, A_c)$, where $A_r$ is its row and $A_c$ is its column. Two cells A and B are adjacent if $|A_r - B_r| + |A_c - B_c| = 1$. Cells in the top and bottom rows are also adjacent, and so are cells in the leftmost and rightmost columns. In other words, $(1, i)$ and $(H, i)$ are adjacent for every $i$ from 1 to W, and $(i, 1)$ and $(i, W)$ are adjacent for every $i$ from 1 to H.

A snake is a sequence of cells $A_1, A_2, \ldots, A_L$, where L is a positive integer equal to its length. No cell appears more than once in the sequence, and any two consecutive cells in the sequence must be adjacent on the board. The maximum possible length is $H \times W$. Cell $A_1$ is the head of the snake.

The player controls only the head, using four commands:

• L: moves the head one column to the left. If the head is in the leftmost column, it moves to the rightmost column of the same row.
• R: moves the head one column to the right. If the head is in the rightmost column, it moves to the leftmost column of the same row.
• U: moves the head one row up. If the head is in the top row, it moves to the bottom row of the same column.
• D: moves the head one row down. If the head is in the bottom row, it moves to the top row of the same column.

After each command, all cells of the snake move at the same time. The head moves as described above, and every other cell follows the cell in front of it. That is, for every i from 2 to L, cell $A_i$ moves to the old position of $A_{i-1}$. For example, if $L \ge 2$, the second cell moves to where the head was. If $L \ge 3$, the third cell moves to where the second cell was.

The game ends as soon as the snake runs into itself, meaning the uniqueness condition fails after a move. This happens when the head moves onto a cell occupied by another part of the snake. In particular, if the snake has at least three cells, a command that moves the head toward $A_2$ causes a collision, because $A_1$ and $A_3$ end up in the same cell.

The classic game also lets the snake eat apples and grow, but this problem does not consider that feature.

In this new version, the player does not press buttons repeatedly. The player places the snake on the board once and writes a program of K commands, which is a sequence of K head moves. When the game starts, the snake carries out the commands in order. If it completes all K commands without a collision, it repeats the same sequence from the beginning. This continues until a collision happens or the player stops watching.

As Konia's lead engineer for snake programming, you must solve the following problem. Given the distinct prime numbers H and W that set the board size, and a command program, find the maximum length of a snake that can be placed on the board so that it never runs into itself after the game starts. The board's management could not explain why H and W must be prime, but they did point out that a prime number has exactly two distinct positive divisors.

The first line contains three integers H, W, and K, the board size and the length of the program. $2 \le H, W \le 10^9 + 9$, $H \ne W$, and $1 \le K \le \min\{100\,000, H \times W\}$.

It is guaranteed that H and W are distinct primes.

The second line contains K characters with no spaces between them. Each character is one of L, R, U, or D.

Print one integer: the maximum length of a snake that can keep moving indefinitely under the given command sequence without running into itself.

In the first test, after all four commands the head returns to its starting cell. So a snake longer than four cells runs into itself within four moves.

In the second test, a correctly placed snake can occupy almost the whole board.