問題文

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

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

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

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

制約

• 入力は全て整数で与えられる
• $1 \leq N \leq 8$
• $- 10 ^ 5 \leq X_i, Y_i \leq 10 ^ 5$
• $(X_i, Y_i) \neq (0, 0)$
• $i \neq j$ なら $(X_i, Y_i) \neq (X_j, Y_j)$

入力

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

出力

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

サンプル

1
1 1

4

訪問の仕方は、$\\$ $(0, 0) → (0, 1) → (1, 1) → (0, 1) → (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) → (1, 0) → (0, 0)\\$ の $4$ 通りです。

8
80322 -49123
-37059 54115
-72232 38756
-64835 55301
-98195 47165
60394 78898
53452 91985
25483 7030

636145057

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