Martian robot P91245


Statement
 

pdf   zip

thehtml
A robot has been sent to the surface of Mars, which for simplicity we consider as an infinite two-dimensional grid. The robot is initially at the (0, 0) cell. We will transmit a sequence of instructions to the robot, each one being ‘L’, ‘R’, ‘U’ or ‘D’ (for left, right, up or down, respectively). For each instruction received by the robot, it will move one step in that direction. For instance, if the robot receives an ‘R’ as its first instruction, it will move to (1, 0).

Since communication with Mars is still complicated, some (or none, or all) of the instructions may be lost. In any case, the relative order of the instructions received by the robot will be preserved. Can you compute the total number of possible final positions of the robot?

For example, suppose that the sequence of instructions is “DRUD”. If the first and the last instructions are lost, then the robot will end at (1, 1) after one move to the right and one upwards. If no instruction is lost, the robot will end at (1, −1), etc.

Input

Input consists of several cases, each one with a string of size between 1 and 104, made up of only letters chosen among ‘L’, ‘R’, ‘U’ and ‘D’.

Output

For every case, print the total number of different positions where the robot may end.

Public test cases

  • Input

    DRUD
R
LLLLL

    Output

    8
2
6
    • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++