OMC073(D)

点数: 400

Writer: potato167

　$4$ つの都市 $A,B,C,D$ があり， はじめは $AB,BC,CD,DA$ 間にそれぞれ道路が $1$ 本ずつあります． ここへ，以下の操作を $10^9+10$ 回繰り返します．

• 異なる $2$ 都市を選び，それらを双方向に結ぶ道路を新たに $1$ 本建設する．

　$10^9+10$ 回の操作の組み合わせは $6^{10^9+10}$ 通りありますが， このうち得られた道路網について， すべての道路をちょうど $1$ 回ずつ通るような道順が存在しないような操作の組み合わせは何通りありますか？ 素数 $10^9+7$ で割った余りを求めてください．

　ただし，道路は交差しないものとし，途中で引き返すことはできないものとします．