One Shared Corridor#13119
A city is represented by a rectangular grid with rows and columns. Rows are numbered from top to bottom, and columns from left to right. Each cell is either free or blocked.
Two couriers need to cross the city. In one step, each courier may move to an adjacent free cell to the right or down.
The first courier starts at and must finish at . The second courier starts at and must finish at .
Two routes are called compatible if their common cells form a single contiguous part of both routes containing at least two cells. This common part may include turns.
Formally, there must be two distinct cells and on both routes such that:
Before cell , the routes have no common cells.
From to , inclusive, the couriers visit exactly the same sequence of cells.
After cell , the routes have no common cells.
Thus, meeting in just one cell is not sufficient. Routes that separate and meet again later are also not compatible.
Find the number of compatible pairs of routes modulo 10^9+7. The couriers are distinct: a pair specifies the route of the first courier and the route of the second courier.
The first line contains two integers and (3\leq h,w\leq2000).
The second line contains four integers a,b,c,d (2\leq a,d\leq w-1; 2\leq b,c\leq h-1).
Each of the next lines contains characters, each either . or #. A dot . denotes a free cell, and # denotes a blocked cell.
The cells , , , and are guaranteed to be free.
Print one integer: the number of compatible pairs of routes modulo 10^9+7. If there are no such pairs, print .
Beispiel 1
Beispiel 2
Beispiel 3
In the first example, there is one compatible pair of routes. Its common part consists of cells and .
In the second example, the routes can only have the single cell in common, so the answer is .
In the third example, there are compatible pairs of routes.
Subtask ( points): h,w\leq6.
Subtask ( points): h,w\leq20.
Subtask ( points): h,w\leq70.
Subtask ( points): \min(h,w)\leq6.
Subtask ( points): there are no blocked cells.
Subtask ( points): a=d or b=c.
Subtask ( points): no additional constraints.