Heidi and Doctor Who need to get to the Cybermen Moonbase before the Cybermen convert all the Swiss cows into Cybercows. They cannot just fly TARDIS directly there, because the Cybermen have already got a hold on the best Swiss watches and created a temporal paradox.
Doctor Who and Heidi have to move the TARDIS by the ticking of the watches, and they only can move on the Moon on an $$$H \times W$$$ grid, numbered $$$1$$$ to $$$H$$$ from bottom to top, and $$$1$$$ to $$$W$$$ from left to right.
They have to be very careful, because the first line of the Moonbase defense consists of $$$N$$$ Cybermen.
Initially (at $$$t = 1$$$) the $$$i$$$-th Cyberman is located at $$$(c_i, r_i)$$$ — $$$c_i$$$-th column, $$$r_i$$$-th row. Fortunately for Doctor Who and Heidi, they are a silly, pre-cyber-war Cybermen, and they move according to a signal from the Moonbase. And fortunately for you, the TARDIS can intercept this signal and send it to you. At the begining, the Cybermen receive from the base a string $$$S$$$ of characters U or D. For each $$$t \in \{ 2, 3, ..., W-1\}$$$, if $$$S[t-1] =$$$ U, then they move up by one grid cell in time step $$$t$$$, and if $$$S[t-1] =$$$ D, then they move down by one grid cell in time step $$$t$$$.
You can help our heroes get to the Moonbase by finding the number of different paths for the Doctor's TARDIS to start in the first column and reach the last column.
The TARDIS must start from any cell in the first column that does not have a Cyberman in it at $$$t = 1$$$. If it is in some cell $$$(c, r)$$$ at time $$$t$$$, then it can move to any cell $$$(c+1, r')$$$ at time $$$t+1$$$ if the new cell does not have any Cyberman at time $$$t+1$$$ and the vertical distance between rows $$$r$$$ and $$$r'$$$ is at most $$$K$$$. The TARDIS must move in each timestep.
The Moon wraps around in the vertical dimension, i.e., if anything goes up from row $$$H$$$, it reaches row $$$1$$$, and if it goes down from row $$$1$$$, it reaches row $$$H$$$.
The first line contains 4 space separated integers, $$$H$$$, $$$W$$$, $$$K$$$, and $$$N$$$ ($$$2 \leq W, H \leq 1000$$$, $$$1 \leq K \leq 10$$$, and $$$0 \leq N \leq 5000$$$).
Each of the next $$$N$$$ lines contain two space-separated integers $$$c_i$$$ and $$$r_i$$$, with ($$$c_i,r_i$$$) indicating the initial position of the $$$i$$$-th Cyberman ($$$1 \leq c_i \leq W$$$, $$$1 \leq r_i \leq H$$$).
Finally, the last line of the input contains a single string of $$$W-1$$$ characters, where $$$S[t-1] \in \{$$$ U, D $$$\}$$$ indicates the Moonbase instructions at time $$$t \in \{2, 3, \dots, W\}$$$.
A single line containing a single integer – the total number of ways (paths) for the TARDIS to go from the first column to the last column using the allowed moves and avoiding all obstacles.
Two paths are considered to be different if they induce different sequences of coordinates.
Since the output can be very large, print it modulo $$$10^9 + 7$$$.
2 2 1 0 U
4
5 4 1 3 1 3 2 2 2 1 UDU
72
5 10 3 10 1 2 2 3 3 4 1 4 1 3 5 1 5 2 5 3 7 1 7 2 UUUDDDUDU
600000
Thanks to your estimates, Doctor Who and Heidi arrived safely to the Cybermen Moonbase. They just need to find the watches before they can fly away saving the cows. But it's too early to celebrate – the base is protected by Cybermen armed with cannons. Fortunately, the Cybermen have poor implementation of the coordinate system, and can only fire along vertical and horizontal directions. Moreover, you have hacked the Cybernetwork and know at what times the Cybermen are going to fire. You can easily save the Doctor and Heidi by calculating a safe path and uploading it to the TARDIS console before any Cyberman has a chance to fire!
You are given a $$$H \times (W + 1)$$$ grid, where the columns are numbered $$$0$$$ to $$$W$$$ (left to right), and the rows are numbered $$$1$$$ to $$$H$$$ (bottom to top).
The TARDIS starts (at $$$t = 0$$$) from cell $$$(0, S)$$$ (i.e., the cell at $$$0$$$-th column, $$$S$$$-th row) and it needs to reach cell $$$(W, E)$$$. At each time step it can move to one of the three adjacent cells in the next column, i.e., if it is in cell $$$(c, r)$$$, it can move to one of $$$(c + 1, r - 1)$$$, $$$(c + 1, r)$$$, or $$$(c + 1, r + 1)$$$ as long as they are within the grid boundary.
There are $$$W$$$ cannons placed just outside the top-boundary, one per each column $$$1, \dots, W$$$ (facing down). Similarly, there are $$$W$$$ cannons just outside the bottom boundary (facing up), and $$$H$$$ more cannons at the right boundary, one per each row $$$1, \dots, H$$$ (facing left). The Cybermen fire cannons fire at arbitrary times. Once fired, the cannonball travels one cell at each time instant in the firing direction.
The total number of cannon firings is $$$N$$$. The $$$i$$$-th cannon fire is described by a tuple $$$(t_i,d_i,p_i)$$$, where $$$t_i$$$ denotes the time of the firing, and $$$d_i \in \{\text{'U', 'D', 'L'}\}$$$ and $$$p_i$$$ indicate which cannon is fired.
- If $$$d_i = \text{'U'}$$$, then the firing cannon is the one facing up at column $$$p_i$$$.
- If $$$d_i = \text{'D'}$$$, it is the one facing down at column $$$p_i$$$.
- If $$$d_i = \text{'L'}$$$, it is the one facing left at row $$$p_i$$$.
Note that $$$t_i$$$ is the time the $$$i$$$-th cannonball first appears in the cell immediately in front of the fired cannon. Before $$$t_i$$$, the $$$i$$$-th cannonball does not exist. E.g. $$$(10, \text{'D'}, 15)$$$ says that the cannon at the top of the $$$15$$$-th column facing down fires, and at $$$t = 10$$$, the cannonball is at $$$(15, H)$$$.
Your task is to find a path of valid moves from $$$(0,S)$$$ to $$$(W,E)$$$ so that the TARDIS does not collide with any cannonball. Keep in mind that cannonballs themselves can collide with each other, and if two or more cannonballs collide, then they vanish from the grid after the collision.
A collision of entities (the TARDIS or cannonballs) can happen:
- If they are in the same cell at time $$$t$$$. Then the collision occurs at time $$$t$$$ and none of them will exist after $$$t$$$.
- If two entities are in two horizontally or vertically adjacent cells at time $$$t$$$, and trying to swap the cells in time $$$t + 1$$$ (i.e., traveling exactly towards each other). In this case the collision occurs between time $$$t$$$ and $$$t+1$$$, and again none of them will exist in time $$$t + 1$$$.
The first line contains 3 space-separated integers, $$$H$$$, $$$W$$$, and $$$N$$$ ($$$2 \leq H \leq 2500$$$, $$$2 \leq W \leq 15000$$$, and $$$1 \leq N \leq 10^6$$$).
The next line contains two space-separated integers $$$S$$$ and $$$E$$$ ($$$1 \leq S, E \leq H$$$).
$$$N$$$ more lines follow, each of which contains an integer $$$t_i$$$ $$$(1 \leq t_i \leq W)$$$, a single upper case letter $$$d_i \in \{ \text{'U', 'D', 'L'}\}$$$, and another integer $$$p_i$$$.
It is guaranteed that if $$$d_i = \text{'L'}$$$, then $$$1 \leq p_i \leq H$$$ and if $$$d_i \in \{\text{'U', 'D'}\}$$$, then $$$1 \leq p_i \leq W$$$.
All tuples $$$(t_i, d_i, p_i)$$$ are distinct.
If there exists a valid path from $$$(0, S)$$$ to $$$(W, E)$$$ that does not collide with a cannonball, output $$$W + 1$$$ lines of integers $$$r_i$$$ which corresponds to the row positions of the path for each column $$$i = 0, \dots, W$$$.
Thus it must hold that $$$r_0 = S$$$, $$$r_W = E$$$, and for all $$$i \gt 0$$$, $$$|r_i - r_{i-1}| \leq 1$$$.
Otherwise, if no valid path exists, output $$$-1$$$.
3 4 1 1 3 1 L 2
1 1 1 2 3
3 4 2 1 3 1 L 2 1 D 3
1 1 2 2 3
3 4 5 1 3 1 L 2 1 D 3 1 U 1 2 D 1 2 D 2
1 2 2 2 3
3 4 7 1 3 1 L 2 1 D 3 1 U 1 2 D 1 2 D 2 2 L 2 2 L 3
-1
Example 1: Here, there are six valid paths and outputting any of them is okay. They are "1 1 1 2 3", "1 1 2 3 3", "1 2 1 2 3", "1 2 2 3 3", "1 2 3 2 3", and "1 2 3 3 3". However, the paths "1 1 2 2 3" and "1 2 2 2 3" are not valid solutions as they would result in a collision of type 2 when traveling from (2, 2) to (3, 2) because the cannonball is traveling from (3,2) to (2,3) at the same time.
Example 2: In this example, the second cannonball collides with the first one at time 2. Hence, in addition to the valid paths of Example 1, the paths "1 1 2 2 3" and "1 2 2 2 3" are also possible in this case.
Example 3: Here, we can no longer use paths "1 1 1 2 3", "1 1 2 3 3", or "1 1 2 2 3" because they collide with the third cannonball in the list. The paths "1 2 3 2 3" and "1 2 3 3 3" are also invalid as they collide with the fifth cannonball in the list.
Example 4: In this last example, it is easy to see that even the remaining three paths of Example 3 are no longer valid, and hence it is impossible for the TARDIS to reach the destination using valid moves.