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