問題文

$H$ 行 $W$ 列のグリッドがあり、上から $i ~ (1 \le i \le H)$ 行目、左から $j ~ (1 \le j \le W)$ 列目のマスをマス $(i, j)$ と表します。 各マスは、障害物マスか空きマスのいずれかの状態です。

あなたは今いるマスから上下左右に隣り合う空きマスに移動することができます。ただし、グリッドの外へ移動することはできません。

$S_i, S_j, G_i, G_j$ が与えられるので、以下の問題を解いてください。

マス $(S_i, S_j), (G_i, G_j)$ を除く $0$ 個以上のマスに障害物を置き、残りのマスを空きマスとしたグリッドは $2^{HW - 2}$ 個存在します。
マス $(S_i, S_j)$ からマス $(G_i, G_j)$ への移動経路のうち、その移動経路が $2^{HW - 2}$ 個のいずれかのグリッドにおいて最短となっている移動経路の個数を求めてください。

制約

• $1 \leq H, W \leq 6$
• $1 \leq S_i, G_i \leq H$
• $1 \leq S_j, G_j \leq W$
• $(S_i, S_j) \neq (G_i, G_j)$
• 入力はすべて整数

入力

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

$H\ W$
$S_i\ S_j$
$G_i\ G_j$

出力

答えを一行に出力せよ。

サンプル

サンプル1

入力サンプルをコピー

入力

2 3
1 1
1 3

出力

2

条件を満たす経路は以下の2つです。

サンプル2

入力サンプルをコピー

入力

2 6
1 1
1 6

出力

11

赤色の経路は最短経路になりません。なぜなら、赤色の経路が存在するグリッドの盤面のとき、青色の経路が最短経路となるため、赤色の経路は最短経路になりえないからです。

6 6
1 1
1 6

1594