Grid Salesman

2 secs 1024 MB
sepa38's icon sepa38

問題文

セパくんはこれから NN 箇所の街を訪問します。訪問する順番は自由ですが、移動距離を最短にしたいです。

ii 番目の町は座標 (Xi,Yi)(X_i, Y_i) にあり、セパくんは最初に原点 (0,0)(0, 0) から出発し、全ての街を訪問した後原点に帰る予定です。 セパくんは上下左右いずれかに 11 ずつ進むことができます。

移動距離が最短である訪問の仕方は何通りか求めてください。 ただし、答えは非常に大きくなる可能性があるので 109+710 ^ 9 + 7 で割った余りを出力してください。

なお、訪問の仕方は、\\ (x1,y1),(x2,y2),...,(xk,yk)(x_1, y_1), (x_2, y_2), ..., (x_k, y_k)\\ という格子点を順にたどったものと\\ (x1,y1),(x2,y2),...,(xk,yk)(x_1', y_1'), (x_2', y_2'), ..., (x_k', y_k')\\ という格子点を順にたどったものについて、 (xi,yi)(xi,yi)(x_i, y_i) \neq (x_i', y_i') となる ii が存在する時、 これらは異なるとします。

制約

  • 入力は全て整数で与えられる
  • 1N81 \leq N \leq 8
  • 105Xi,Yi105- 10 ^ 5 \leq X_i, Y_i \leq 10 ^ 5
  • (Xi,Yi)(0,0)(X_i, Y_i) \neq (0, 0)
  • iji \neq j なら (Xi,Yi)(Xj,Yj)(X_i, Y_i) \neq (X_j, Y_j)

入力

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

NX1    Y1          XN    YNN\\ X_1 \;\; Y_1\\ \;\;\;\;\; ⋮\\ X_N \;\; Y_N\\

出力

計算結果を一行に出力してください。

サンプル

入力1
1
1 1
出力1
4

訪問の仕方は、\\ (0,0)(0,1)(1,1)(0,1)(0,0)(0, 0) → (0, 1) → (1, 1) → (0, 1) → (0, 0)\\ (0,0)(0,1)(1,1)(1,0)(0,0)(0, 0) → (0, 1) → (1, 1) → (1, 0) → (0, 0)\\ (0,0)(1,0)(1,1)(0,1)(0,0)(0, 0) → (1, 0) → (1, 1) → (0, 1) → (0, 0)\\ (0,0)(1,0)(1,1)(1,0)(0,0)(0, 0) → (1, 0) → (1, 1) → (1, 0) → (0, 0)\\44 通りです。

入力2
8
80322 -49123
-37059 54115
-72232 38756
-64835 55301
-98195 47165
60394 78898
53452 91985
25483 7030
出力2
636145057

109+710 ^ 9 + 7 で割った余りを出力することに注意してください。

Submit


Go (1.21)