← 返回题目列表

Codeforces · 404/E

E. 1D 迷宫

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

Valera 有一条双向无限长的条带,由细胞组成。单元格按整数编号。 0号牢房有一个机器人。

机器人有指令——他必须执行的动作顺序。在一次移动中,机器人根据指令向左移动一个单元或向右移动一个单元。在机器人开始移动之前,Valera 在条带的某些单元格中放置了障碍物,不包括 0 号单元格。如果机器人按照指令进入有障碍物的单元格,它将跳过此移动。

Valera 还指示机器人在完成整个指令后必须进入的完成单元。结束单元格应该与起始单元格不同。据信,如果机器人在移动过程中恰好访问过终点单元一次(在最后一次移动时),则机器人成功完成了指令。而且,后一招是不能跳过的。

让我们假设 k 是 Valera 必须放置的最小障碍物数量,以使机器人能够成功完成整个指令序列并最终进入某个完成单元。您需要计算 Valera 可以通过多少种方式选择 k 个障碍物和完成单元,以便机器人能够成功完成指令。

输入

第一行包含不带空格的字符序列 s1s2... sn (1 ≤ n ≤ 106),仅由字母“L”和“R”组成。如果字符 si 等于“L”,则第 i 次移动的机器人必须尝试向左移动一个单元格。如果第 si 个字符等于“R”,则第 i 次移动的机器人必须尝试向右移动一个单元格。

输出

打印单个整数 — 所需的方式数。保证该数字符合 64 位有符号整数类型。

示例

输入 #1

RR

输出 #1

1

输入 #2

RRL

输出 #2

1

注意

在第一个示例中,Valera 不得添加任何障碍物,并且他的完成单元格必须是单元格 2。

在第二个示例中,Valera 必须在 1 号单元格中添加障碍物,并且他的结束单元格必须为 - 1 号单元格。在这种情况下,机器人会跳过前两次移动,在第三次移动时,他会直接从起始单元格移动到结束单元格。但是,如果 Valera 不添加任何障碍物,或者向另一个单元添加障碍物,则机器人会多次访问完成单元。