← 返回题目列表

Codeforces · 611/F

F. 新年和清洁

中文机器翻译题面 查看原题

Limak 是一只小北极熊。他的父母让他在除夕之前打扫房子。他们的房子是一个长方形网格,有 h 行和 w 列。每个单元格都是一个空的正方形。

他是一只小熊,因此他不能自己打扫房子。相反,他将使用清洁机器人。

清洁机器人有一个内置的 n 个动作模式,由长度为 n 的字符串定义。单次移动(角色)即可将机器人移动到四个相邻单元之一。每个字符都是以下四个字符之一:“U”(上)、“D”(下)、“L”(左)、“R”(右)。一个动作需要一分钟。

必须在某个单元格中放置并启动清洁机器人。然后它重复其移动模式,直到撞到墙壁(房子的四个边界之一)。撞到墙上后可以放置并再次使用。

Limak 不确定将清洁机器人放在一个牢房中是否足够。因此,他将启动它 w·h 次,每个牢房一次。也许有些细胞会被多次清洁,但谁在乎呢?

Limak 问你一个问题。打扫房子需要多长时间?查找并打印以 109 + 7 为模的分钟数。也有可能清洁机器人永远不会停止,然后打印“-1”(不带引号)。

放置和启动机器人不需要时间,但是,当机器人撞到墙壁时,您必须计算一次移动。查看示例以进一步说明。

输入

第一行包含三个整数 n、h 和 w (1 ≤ n, h, w ≤ 500 000) - 分别是模式的长度、行数和列数。

第二行包含长度为 n 的字符串 — n 个动作的模式。每个字符都是大写字母“U”、“D”、“L”或“R”之一。

输出

打印一行答案。

如果清洁机器人永远不会停止,请打印“-1”(不带引号)。否则,打印清洁房屋所需的分钟数模 109 + 7。

示例

输入 #1

1 10 2
R

输出 #1

30

输入 #2

3 4 6
RUL

输出 #2

134

输入 #3

4 1 500000
RLRL

输出 #3

-1

注意

第一个样板房是一个 10 行 2 列的网格。在第二列的任何位置启动机器人只会导致一次移动(因此,清洁一分钟),其中机器人会撞到墙上 - 他试图向右走,但没有第三列。在第一列的任意位置启动机器人将导致两次移动。总分钟数为 10·1 + 10·2 = 30。

在第二个示例中,启动的机器人将尝试移动“RULRULRULR...”例如,对于第二排最左边的单元,机器人将进行 5 次移动,然后由于撞到上墙而停止。