Maze 1D

题意翻译

一个机器人在数轴上的0点。给一串指令，机器人按照指令走。为了使机器人最后一步走到一个从来没来过的位置，我们可以在数轴上放石头。每次机器人被石头卡住他就跳过当前的那个指令。问：最少使用石头的前提下，一共有几种放石头方法。

题目描述

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.

输入输出格式

输入格式

The first line contains a sequence of characters without spaces $ s_{1}s_{2}...\ s_{n} $ $ (1<=n<=10^{6}) $ , 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.

输出格式

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

输入输出样例

输入样例 #1

RR

输出样例 #1

1

输入样例 #2

RRL

输出样例 #2

1

说明

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.