Problem:

Problem D: Gridgedge

Problem

 左上が$(0, 0)$、 右下が$(R-1, C-1)$である$R \times C$マスのグリッドがある。あるマス($e$, $f$)にいるとき、そこから$(e+1, f)$, $(e-1, f)$, $(e, f+1)$, $(e, f-1)$, $(e, 0)$, $(e, C-1)$, $(0, f)$, $(R-1, f)$にはコスト$1$で移動できる。ただしグリッドの外に出ることはできない。マス$(a_i, a_j)$から$(b_i, b_j)$へ移動するとき、最短経路のコストと、最短経路の組み合わせの総数を$10^9 + 7$で割った余りを計算せよ。

ただし、経路の組み合わせは移動の方法によって区別するものとする。たとえば、現在地が$(100, 1)$ のとき、 $(100, 0)$に最短コストで行くには上記$(e, f-1)$か$(e, 0)$で行くことができるので、$2$通りと数える。

Input

入力は以下の形式で与えられる。

$R$ $C$ $a_i$ $a_j$ $b_i$ $b_j$

Constraints

入力は以下の条件を満たす。

    
$1 \le R, C \le 500$

    
$0 \le a_i, b_i \le R - 1$

    
$0 \le a_j, b_j \le C - 1$

    
与えられる入力は全て整数である。

Output

マス$(a_i, a_j)$から$(b_i, b_j)$へ移動するとき、最短経路のコストと、最短経路の組み合わせの総数を$10^9+7$で割った余りを空白区切りで$1$行に出力せよ。

Sample Input 1

2 2 0 0 1 1

Sample Output 1

2 8

Sample Input 2

1 1 0 0 0 0

Sample Output 2

0 1

Sample Input 3

1 10 0 0 0 9

Sample Output 3

1 1

Sample Input 4

5 5 0 0 4 4

Sample Output 4

2 2

Sample Input 5

421 435 196 169 388 9

Sample Output 5

43 917334776



Sample input:
2 2 0 0 1 1


Sample output:
2 8

Submission status: Accepted

Solution code:
from collections import deque
R,C,ay,ax,by,bx = map(int,input().split())

MOD = INF = 10**9+7
dists = [[INF]*C for i in range(R)]
dists[ay][ax] = 0
ptns = [[0]*C for i in range(R)]
ptns[ay][ax] = 1
q = deque([(0,ax,ay)])
dxs = [1,0,-1,0]
dys = [0,1,0,-1]
ans_d = None
while q:
    d,x,y = q.popleft()
    if ans_d is not None and d > ans_d:
        break
    if (x,y) == (bx,by):
        ans_d = d
    if d > dists[y][x]: continue
    dists[y][x] = d
    for dx,dy in zip(dxs,dys):
        nx,ny = x+dx, y+dy
        if not(0 <= nx < C) or not(0 <= ny < R): continue
        if d+1 > dists[ny][nx]: continue
        if dists[ny][nx] == INF:
            q.append((d+1,nx,ny))
            dists[ny][nx] = d+1
        ptns[ny][nx] += ptns[y][x]
        ptns[ny][nx] %= MOD
    for nx,ny in ((x,0),(x,R-1),(0,y),(C-1,y)):
        if d+1 > dists[ny][nx]: continue
        if dists[ny][nx] == INF:
            q.append((d+1,nx,ny))
            dists[ny][nx] = d+1
        ptns[ny][nx] += ptns[y][x]
        ptns[ny][nx] %= MOD

print(ans_d, ptns[by][bx] % MOD)