406122: GYM102271 A The Cybermen Moonbase (Easy)

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