CF404E.Maze 1D

Valera has a strip infinite in both directions and consisting of cells. The cells are numbered by integers. The cell number 0 has a robot.

The robot has instructions — the sequence of moves that he must perform. In one move, the robot moves one cell to the left or one cell to the right, according to instructions. Before the robot starts moving, Valera puts obstacles in some cells of the strip, excluding cell number 0. If the robot should go into the cell with an obstacle according the instructions, it will skip this move.

Also Valera indicates the finish cell in which the robot has to be after completing the entire instructions. The finishing cell should be different from the starting one. It is believed that the robot completed the instructions successfully, if during the process of moving he visited the finish cell exactly once — at its last move. Moreover, the latter move cannot be skipped.

Let's assume that k is the minimum number of obstacles that Valera must put to make the robot able to complete the entire sequence of instructions successfully and end up in some finishing cell. You need to calculate in how many ways Valera can choose k obstacles and the finishing cell so that the robot is able to complete the instructions successfully.

瓦列拉有一条向左右两个方向无限延伸的格子带，格子按整数编号。编号为 $0$ 的格子上有一个机器人。

机器人拥有一组指令——即它必须执行的一系列移动操作。每次移动，机器人根据指令向左或向右移动一个格子。在机器人开始移动前，瓦列拉会在格子带上的一些格子中放置障碍物（但编号为 $0$ 的起始格子除外）。若机器人根据指令本应移入一个有障碍物的格子，则该次移动将被跳过。

此外，瓦列拉还需指定一个终点格子，即机器人在执行完全部指令后必须到达的位置。该终点格子必须与起始格子（编号 $0$）不同。我们认为机器人成功完成了全部指令，当且仅当：在整个移动过程中，它恰好访问终点格子一次，且这次访问发生在最后一次移动时；并且，最后一次移动不能被跳过。

设 $k$ 为瓦列拉为使机器人能成功完成全部指令并抵达某个终点格子所必须放置的最少障碍物数量。你需要计算：瓦列拉有多少种方式选择这 $k$ 个障碍物以及终点格子，使得机器人能够成功完成指令。

The first line contains a sequence of characters without spaces _s_1_s_2... s__n (1 ≤ n ≤ 106), consisting only of letters "L" and "R". If character s__i equals "L", then the robot on the i-th move must try to move one cell to the left. If the s__i-th character equals "R", then the robot on the i-th move must try to move one cell to the right.

第一行包含一个不含空格的字符序列 $s_1s_2\ldots s_n$（$1 \leq n \leq 10^6$），该序列仅由字母 "L" 和 "R" 组成。若字符 $s_i$ 为 "L"，则机器人在第 $i$ 步移动时需尝试向左移动一格；若第 $i$ 个字符 $s_i$ 为 "R"，则机器人在第 $i$ 步移动时需尝试向右移动一格。

Print a single integer — the required number of ways. It's guaranteed that this number fits into 64-bit signed integer type.

输出一个整数——即所求的方案数。保证该数在 64 位有符号整数类型范围内。

In the first sample Valera mustn't add any obstacles and his finishing cell must be cell 2.

In the second sample, Valera must add an obstacle in cell number 1, and his finishing cell must be cell number  - 1. In this case robot skips the first two moves and on the third move he goes straight from the starting cell to the finishing one. But if Valera doesn't add any obstacles, or adds an obstacle to another cell, then the robot visits the finishing cell more than once.

在第一个样例中，瓦莱拉不能添加任何障碍物，且他的终点单元格必须是第 2 号单元格。

在第二个样例中，瓦莱拉必须在第 1 号单元格处添加一个障碍物，且他的终点单元格必须是第 $-1$ 号单元格。此时，机器人会跳过前两次移动，并在第三次移动时直接从起始单元格移动到终点单元格。但如果瓦莱拉不添加任何障碍物，或在其他单元格添加障碍物，则机器人会多次访问终点单元格。