AT_apc001_i Simple APSP Problem

[problemUrl]: https://atcoder.jp/contests/apc001/tasks/apc001_i $ H\ \times\ W $ のマス目が与えられます。 左上隅のマス目を $ (0,\ 0) $、右下隅のマス目を $ (H-1,\ W-1) $ と表すことにします。 マス目のうち、$ N $ 個のマス目 $ (x_1,\ y_1),\ (x_2,\ y_2),\ ...,\ (x_N,\ y_N) $ は黒く塗られており、残りは白く塗られています。 白いマス目 $ A,\ B $ の間の最短距離を、$ A $ から $ B $ まで**白いマス目のみ**を使用して移動するときの最短移動回数とします。 ただし、$ 1 $ 回の移動では、上下左右の隣りあったマス目に移動できるものとします。 白いマス目は全部で $ H\ ×\ W\ -\ N $ 個あるため、白いマス目から $ 2 $ つマス目を選ぶ方法は $ _{(H×W-N)}C_2 $ 通りあります。 この $ _{(H×W-N)}C_2 $ 通りそれぞれについて、選んだマスの間の最短距離を求め、 それを全て足して $ 1,000,000,007=10^9+7 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ N $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ $ : $ $ x_N $ $ y_N $

最短距離の総和を $ 10^9+7 $ で割った余りを出力してください。

### 制約 - $ 1\ \leq\ H,\ W\ \leq\ 10^6 $ - $ 1\ \leq\ N\ \leq\ 30 $ - $ 0\ \leq\ x_i\ \leq\ H-1 $ - $ 0\ \leq\ y_i\ \leq\ W-1 $ - $ i\ \neq\ j $ ならば、$ x_i\ \neq\ x_j $ または $ y_i\ \neq\ y_j $ - 白いマス目が $ 1 $ つ以上存在する - 全ての白いマス目 $ A,\ B $ について、白いマス目のみを使用して $ A $ から $ B $ へ移動できる ### Sample Explanation 1 マス目の色は以下のようになっています(`.`: 白いマス目, `#`: 黒いマス目)。 ``` ... .#. ``` ここで，以下のように白いマス目にアルファベットを振ります。 ``` ABC D#E ``` すると， - dist(A, B) = $ 1 $ - dist(A, C) = $ 2 $ - dist(A, D) = $ 1 $ - dist(A, E) = $ 3 $ - dist(B, C) = $ 1 $ - dist(B, D) = $ 2 $ - dist(B, E) = $ 2 $ - dist(C, D) = $ 3 $ - dist(C, E) = $ 1 $ - dist(D, E) = $ 4 $ であり，これらの総和は $ 20 $ となります。 ただし，dist(A, B) はマス目A, Bの最短距離とします。 ### Sample Explanation 2 以下のように白いマス目にアルファベットを振ります。 ``` ABC DE# ``` すると， - dist(A, B) = $ 1 $ - dist(A, C) = $ 2 $ - dist(A, D) = $ 1 $ - dist(A, E) = $ 2 $ - dist(B, C) = $ 1 $ - dist(B, D) = $ 2 $ - dist(B, E) = $ 1 $ - dist(C, D) = $ 3 $ - dist(C, E) = $ 2 $ - dist(D, E) = $ 1 $ であり，これらの総和は $ 16 $ となります。