## Castle

View as PDF

Points: -1
Time limit: 2.0s
Memory limit: 256M

Problem types

A rook stands on a $$\mathbf{N\times M}$$ chessboard whose each square has a letter which is one of the ($$R,\ L,\ U,\ D$$). These letters refer to which way the rook can move:

• $$R$$ refers to Right
• $$L$$ refers to Left
• $$U$$ refers to Up
• $$D$$ refers to Down

The goal of the rook is to reach the target location from its current location by making the least moves. How many different ways can the rook move from its current location to its target location with the $$\underline{least}$$ moves?

You can check rook's wiki page to learn how it moves.

#### Input

First line contains 2 integers. The first integer $$\mathbf{N}$$ is number of rows of the chessboard, and the second integer $$\mathbf{M}$$ is number of columns of the chessboard.

• $$1\leq\mathbf{N,M}\leq 500$$

Next $$\mathbf{N}$$ lines consist of $$\mathbf{M}$$ letters, one of the ($$R,\ L,\ U,\ D$$), which refer to ways the rock can move.

$$\mathbf{(N+2)}^{th}$$ line contains 2 integers, the Start coordinates. (The first integer indicates to $$\mathbf{Y}$$, the second number indicates to $$\mathbf{X}$$.)

• $$1\leq\mathbf{Y_{start}}\leq N$$
• $$1\leq\mathbf{X_{start}}\leq M$$

$$\mathbf{(N+3)}^{th}$$ line contains 2 integers, the End coordinates. (The first integer indicates to $$\mathbf{Y}$$, the second number indicates to $$\mathbf{X}$$.)

• $$1\leq\mathbf{Y_{end}}\leq N$$
• $$1\leq\mathbf{X_{end}}\leq M$$

It is guaranteed that Start and End coordinates will be different from each other.

#### Output

Print the different ways the rook can move from its location to the target location with the least amount of moves modulo $$10^9+7$$.

If there is no path, print $$\mathbf{0}$$.

#### Examples

Input 1:

3 2
R D
R D
L R
1 1
3 2

Output 1:

1

Input 2:

3 3
R D D
D R D
R L L
1 1
3 1

Output 2:

2

#### Explanation

The coordinates of the castle is written in $$(Y\ X)$$ syntax

##### Input 1

The shortest path can only be created in 1 way with 2 steps.

• It starts from $$(1\ 1)$$.
• From $$(1\ 1)$$ it goes right to $$(1\ 2)$$.
• From $$(1\ 2)$$ it goes down to $$(3\ 2)$$.
##### Input 2

The shortest path can only be created in 2 ways with 3 steps.

• Way 1:
• It starts from $$(1\ 1)$$.
• From $$(1\ 1)$$ it goes right to $$(1\ 2)$$.
• From $$(1\ 2)$$ it goes down to $$(3\ 2)$$.
• From $$(3\ 2)$$ it goes left to $$(3\ 1)$$.
• Way 2:
• It starts from $$(1\ 1)$$.
• From $$(1\ 1)$$ it goes right to $$(1\ 3)$$.
• From $$(1\ 3)$$ it goes down to $$(3\ 3)$$.
• From $$(3\ 3)$$ it goes left to $$(3\ 1)$$.