Problem: 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.

Input

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

Output

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

Examples

Input

RR


Output

1


Input

RRL


Output

1

Note

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.

Solution (in JAVA):

Solution:
import java.io.*;
import java.text.DecimalFormat;
import java.util.*;

public class Main {

    public static final DecimalFormat DF_3 = new DecimalFormat("0.000");


    static int[] readArray(int size, InputReader in, boolean subOne) {
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i] = in.nextInt() + (subOne ? -1 : 0);
        }
        return a;
    }

    static long[] readLongArray(int size, InputReader in) {
        long[] a = new long[size];
        for (int i = 0; i < size; i++) {
            a[i] = in.nextLong();
        }
        return a;
    }

    static void sortArray(int[] a) {
        Random random = new Random();

        for (int i = 0; i < a.length; i++) {
            int randomPos = random.nextInt(a.length);
            int t = a[i];
            a[i] = a[randomPos];
            a[randomPos] = t;
        }
        Arrays.sort(a);
    }

    public static final Comparator<long[]> PAIR_COMPARATOR = (o1, o2) -> {
        if (o1[0] == o2[0]) {
            return Long.compare(o1[1], o2[1]);
        }
        return Long.compare(o1[0], o2[0]);
    };


    public static void main(String[] args) throws FileNotFoundException {
//        InputReader in = new InputReader(new FileInputStream("input.txt"));
//        PrintWriter out = new PrintWriter(new BufferedOutputStream(new FileOutputStream("milkvisits.out")));
//
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

//        long start = System.currentTimeMillis();

        String s = in.nextString();
        int n = s.length();
        int[] a = new int[n];
        boolean allOne = true;
        for (int i = 0; i < n; i++) {
            a[i] = s.charAt(i) == s.charAt(0) ? 1 : -1;
            if (a[i] != 1) {
                allOne = false;
            }
        }
        if (allOne || checkNoBorder(a)) {
            out.println(1);
            out.close();
            return;
        }
        int ans = solve(a);

        for (int i = 0; i < n; i++) {
            a[i] = s.charAt(i) != s.charAt(0) ? 1 : -1;
        }

        ans += solve(a);


        out.println(ans);


        out.close();
    }

    private static int solve(int[] a) {
        int max = 0;
        int min = 0;
        int current = 0;
        for (int i = 0; i < a.length; i++) {
            current += a[i];
            max = Math.max(max, current);
            min = Math.min(min, current);
        }

        int r = max + 1;
        int l = 0;
        while (r - l > 1) {
            int m = (r + l) / 2;
            if (check(a, m)) {
                l = m;
            } else {
                r = m;
            }
        }
        return l;
    }

    private static boolean check(int[] a, int top) {
        int end = 0;
        for (int i = 0; i < a.length; i++) {
            end += a[i];
            if (end >= top) {
                end--;
            }
        }

        int current = 0;
        if (current <= end) {
            return false;
        }
        for (int i = 0; i < a.length - 1; i++) {
            current += a[i];
            if (current >= top) {
                current--;
            }
            if (current <= end) {
                return false;
            }
        }
        return true;
    }

    private static boolean checkNoBorder(int[] a) {
        int last = 0;
        for (int i = 0; i < a.length; i++) {
            last += a[i];
        }
        if (last == 0) {
            return false;
        }

        int current = 0;
        for (int i = 0; i < a.length - 1; i++) {
            current += a[i];
            if (current == last) {
                return false;
            }
        }
        return true;
    }

    private static int[] getBinary(long a, int size) {
        int[] result = new int[size];
        for (int i = 0; i < size; i++) {
            result[i] = (int) ((a >> i) & 1);
        }
        return result;
    }


    private static void outputArray(long[] ans, PrintWriter out, boolean addOne) {
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < ans.length; i++) {
            long an = ans[i] + (addOne ? 1 : 0);
            str.append(an).append(' ');
        }
        out.println(str);
    }

    private static void outputArray(List<Integer> ans, PrintWriter out, boolean addOne) {
        StringBuilder str = new StringBuilder();
        for (int j = 0; j < ans.size(); j++) {
            long i = ans.get(j);
            long an = i + (addOne ? 1 : 0);
            str.append(an);
            if (j < ans.size() - 1) {
                str.append(' ');
            }
        }
        out.println(str);
//        out.flush();
    }

    private static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextString() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public char nextChar() {
            return next().charAt(0);
        }

        public String nextWord() {
            return next();
        }

        private List<Integer>[] readTree(int n) {
            return readGraph(n, n - 1);
        }

        private List<Integer>[] readGraph(int n, int m) {
            List<Integer>[] result = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                result[i] = new ArrayList<>();
            }
            for (int i = 0; i < m; i++) {
                int u = nextInt() - 1;
                int v = nextInt() - 1;
                result[u].add(v);
                result[v].add(u);
            }
            return result;
        }

    }
}