E. Лабиринт 1D
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Валеры есть бесконечная в обе стороны полоска, состоящая из клеток. Клетки пронумерованы целыми числами. В клетке с номером 0 стоит робот.

У робота есть инструкция — последовательность ходов, которые он должен совершить. За один ход робот перемещается на одну клетку влево или вправо, согласно инструкции. До начала движения робота Валера размещает препятствия в каких-то клетках полоски, исключая клетку с номером 0. Если в какой-то из ходов робот по инструкции должен пойти в клетку с препятствием, то он пропускает этот ход.

Кроме того Валера указывает номер финишной клетки, в которой робот должен оказаться после выполнения всей инструкции. Финишная клетка должна быть отлична от стартовой. Считается, что робот успешно выполнил инструкцию, если в процессе ее выполнения он посетил финишную клетку ровно один раз — своим последним ходом. Причем, последний ход не должен быть пропущен.

Предположим, что минимальное количество препятствий, которое необходимо поставить Валере, чтобы робот смог выполнить всю последовательность ходов и оказаться в какой-то финишной клетке равно k. Вам требуется посчитать, сколькими способами Валера может выбрать k препятствий и финишную клетку так, чтобы робот смог успешно выполнить инструкцию.

Входные данные

В первой строке записана последовательность символов без пробелов s1s2... sn (1 ≤ n ≤ 106), состоящая только из букв «L» и «R». Если символ si равен «L», то робот на i-м ходу должен попробовать переместиться на одну клетку влево. Если символ si равен «R», то робот на i-м ходу должен попробовать переместиться на одну клетку вправо.

Выходные данные

Выведите целое число — требуемое количество способов. Гарантируется, что это число помещается в 64-битном знаковом целочисленном типе данных.

Примеры
Входные данные
RR
Выходные данные
1
Входные данные
RRL
Выходные данные
1
Примечание

В первом примере Валера не должен ставить никаких препятствий, а в качестве финишной клетки выбрать клетку с номером 2.

Во втором примере Валере необходимо поставить препятствие в клетку с номером 1, а финишной клеткой назначить клетку с номером  - 1. В этом случае он пропустит первые два хода, а на третьем сразу перейдет из своей стартовой клетки в финишную. Если же Валера не поставит никаких препятствий, или поставит препятствие в другую клетку, то он посетит финишную клетку более одного раза.