CF404E Maze 1D

Valera 有一条无限延伸的纸带，由若干格子组成。这些格子按整数编号。机器人最初位于编号为 $0$ 的格子。 机器人有一份指令序列——即它需要执行的一系列移动。每次移动，机器人会根据指令向左或向右移动一个格子。在机器人开始移动前，Valera 会在纸带上的某些格子放置障碍物（初始格子 $0$ 不能放障碍物）。如果根据指令，机器人应该进入带有障碍物的格子，则本次移动会被跳过。 此外，Valera 还会指定一个终点格子，要求机器人在执行全部指令后正好位于该格子。终点必须与初始格子不同。当且仅当机器人恰好在最后一步第一次访问终点格子，并完成所有指令，且最后一步不能被跳过时，才认为机器人成功完成指令。 设 $k$ 为 Valera 至少需要放置的障碍物数目，使机器人能够如上完成所有指令并停在某个终点格子。请你计算，对于多少种方式，可以选择 $k$ 个障碍物及终点格子，使机器人能够成功完成全部指令。

第一行为一个无空格的字符序列 $s_{1}s_{2}\ldots s_{n}$（$1 \leq n \leq 10^6$），仅由字母 "L" 和 "R" 组成。若 $s_i$ 为 "L"，则机器人在第 $i$ 步尝试向左移动一格；若 $s_i$ 为 "R"，则尝试向右移动一格。

输出一个整数，即所需方案数。保证答案不会超过 $64$ 位有符号整数范围。

在第一个样例中，Valera 不需要放置任何障碍物，终点格子应该选为 $2$。 在第二个样例中，Valera 必须在编号为 $1$ 的格子放置一个障碍物，终点应为 $-1$。此时机器人会跳过前两个动作，并在第三步直接从起点移动到终点。如果 Valera 不放置障碍物，或者障碍物放在其他格子，机器人会多次经过终点格子。 由 ChatGPT 5 翻译