Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Brownian Motion

By shhrrtnvr · Limits 1s, 512 MB

Microscopic particles suspended on any fluid has a chaotic behavior since they do not stay at same location. Every moment they experience a number of collisions with fluid molecules from different directions. As a result of these collisions,the particle moves randomly as if it is confused all the time. In physics, this phenomenon is known as Brownian Motion named after the Scottish botanist Robert Brown who first described the phenomenon in 1827. Then, almost 80 years later, in 1905, Albert Einstein published a paper explaining Brownian Motion to establish the idea of existence of atoms and molecules. Now, more than 100 years later, with advancements of computer science, modeling the physical phenomena has become an important task for physicists. Since you are a great programmer and love to solve challenging problems, a group of physicists from your country came to you to help them solve this problem regarding Brownian Motion.

For a particle placed on the water surface, the physicists want to know the probability of the particle reaching another point on the surface after a certain amount of time. To model the scenario they imagined the surface of the fluid as a two-dimensional grid and each cell of the grid represents a point on the fluid surface. At each millisecond, the particle moves from one cell to any of its eight neighbor cells. The surface is a closed system, therefore, particles can not escape by crossing the boundary of the grid.

Initially, the surface is divided into an n×nn\times n grid, where, 1<n1001 \lt n \le 100. Cells are identified with the their row and column number as (r,c)(r,c) where 0r,c<n0\le r, c \lt n. If a particle is located at (r,c)(r,c), after a millisecond it must move to any of the following cells (r,c+1)(r, c+1), (r,c1)(r,c-1), (r+1,c)(r+1, c), (r+1,c+1)(r+1, c+1), (r+1,c1)(r+1,c-1), (r1,c)(r-1, c), (r1,c+1)(r-1, c+1), (r1,c1)(r-1, c-1). You will be given the initial position (ri,ci)(r_i, c_i)and final position (rf,cf)(r_f, c_f). You have to find the probability of reaching from (ri,ci)(r_i, c_i) to (rf,cf)(r_f, c_f) after tt milliseconds, where, 0t1030\le t \le 10^3.

The probability can be represented as PQ\frac{P}{Q} where P,QP, Q are co-prime integers. Let, Q1Q^{-1} be an integer for which Q.Q11(mod109+7)Q.Q^{-1} \equiv 1 \pmod{10^9+7}. You have to print P.Q1(mod109+7)P.Q^{-1} \pmod{10^9+7}.

Input

The input consist of two lines.

First line of input contains two integers nn(1<n100)(1\lt n \le 100) and tt(0t103)(0\le t \le 10^3) separated by space.

Following line contains 4 integers ri,ci,rf,cfr_i, c_i, r_f, c_f (0ri,ci,rf,cf<n)(0 \le r_i, c_i, r_f, c_f \lt n) separated by space.

Output

Print a single integer, the probability of reaching initial to final cell after tt milliseconds as P.Q1(mod109+7)P.Q^{-1} \pmod{10^9+7}.

Samples

InputOutput
6 0
2 3 2 3
1
InputOutput
60 110
4 40 2 56
448675357
InputOutput
4 2
1 1 2 2
281250002

Note: The particle must move after a millisecond. It can not stay at the same cell for more than 1 millisecond.

    Discussion

    Statistics


    100% Solution Ratio

    Saadmaan007Earliest, 1M ago

    Saadmaan007Fastest, 0.9s

    Saadmaan007Lightest, 82 MB

    Saadmaan007Shortest, 820B

    Submit

    Login to submit