Martian robot (2) P57361


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.

For example, suppose that the transmitted sequence of instructions is “DRUD”. There are 24 = 16 possible sequences of instructions received, because every single instruction may be lost or not. 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. This is the only way that the robot may end there. By contrast, the robot will end at (1, −1) if no instruction is lost, if the robot receives “DR” or if it receives “RD”. For this example, there are four positions where the robot may end in exactly one way, and four positions where the robot may end in exactly three ways.

Can you compute that information? For the example above, you should print 

1 4
3 4

That is, for every possible number of ways n, in increasing order, print how many positions have n ways to end there.

Input

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

Output

For every case, print the information mentioned above. Since the number of ways of ending at a certain position may get very big, make the computations modulo 108 + 7. Print a line with 10 dashes at the end of each case.

Public test cases

  • Input

    DRUD
R
LLLLL
DDDDDDDDDDDDDDDDDDUUUUUUUUUUUUUUUUUU

    Output

    1 4
3 4
----------
1 2
----------
1 2
5 2
10 2
----------
1 2
36 2
630 2
7140 2
58905 2
376992 2
805254 2
1947792 2
7871599 2
8347680 2
10789439 2
30260340 2
51677616 2
54186842 2
67902175 2
75134670 1
94143280 2
96296941 2
97496005 2
----------
    • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++