AT_colopl2018_final_d Chaos of the Snuke World

[problemUrl]: https://atcoder.jp/contests/colopl2018-final/tasks/colopl2018_final_d *――世界に散らばる石板を集めよ。混沌の内に順序を与えよ。さらば、光はあたえられん――* 高橋君の、パズル RPG 「Chaos of the Snuke World」のプレイは、今やクライマックスに差し掛かろうとしています。 このゲームの舞台は、遠い昔に魔法文明の栄えた帝国です。今から千二百年前、恐怖政治を敷いた時の皇帝に対するクーデターにより、市民が政権を掌握しました。 彼らは、今後このような権力者が誕生しないように、皇帝の権力の源であった魔法の石板を各地に分散させることにしました。しかし皮肉なことに、まさにこのことによって 魔力による国の結束に綻びが生じ、中央も地方も見境なく滅び、そして石板の置かれた場所も忘れ去られてしまいました。 主人公は、豊かだった魔法帝国の復活を夢見る少年です。高橋君の操作するこの少年は、各地の村を、森を、洞窟を巡り、ついに石板をすべて集めたのでした。 **石板は全部で $ N $ 枚あり、$ i $ 個目の石板の表には整数 $ A_i $ が、裏には整数 $ B_i $ が書かれています。** さて、古都に戻ってきた少年のするべきことは、あとは廃墟と化した宮廷の最奥にある台に石板を並べることだけです。しかしここに、最後にして最大の難関があるのでした。 台には石板を横一列に並べることができます。少年は、台に石板を自由な順番で、どちらかの面を上にして並べることができます。少年が石板をすべて並べ終わると、 政権を建てた市民らのかけた古代の呪いが発動し、石板の裏表をひっくり返してしまうことがあるのです。どの位置の石板も、ちょうど半分の確率でひっくり返されてしまいます。 その後少年は、隣り合う石板同士を入れ替える操作を何度でも行うことができます。少年が石板を、上の面に書かれた整数が左から広義単調増加になるように並べることができたなら、 人々が豊かに暮らした帝国は復活し、少年の夢は叶うのです。しかし、もしこの操作に手間取ってしまえば……古代魔法が発動し、石板は再び散逸してしまうのです！ 石板が散逸してしまえば、少年は再び石板を集めなおさなければなりません。早くゲームをクリアしたい高橋君は、隣り合う石板同士を入れ替える操作の必要回数の期待値が 最小になるように、石版を台に並べていくことにしました。 高橋君はゲームのやりすぎで、目が疲れています。高橋君のために、操作の必要回数の期待値の最小値を $ 2^N $ 倍した値(この値は整数であることが証明できます)を $ 10^9+7 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ B_1 $ : $ A_N $ $ B_N $

操作の必要回数の期待値の最小値の $ 2^N $ 倍を $ 10^9+7 $ で割ったあまりを出力せよ。

### 制約 - $ 1\leq\ N\leq\ 10^5 $ - $ 1\leq\ A_i,B_i\leq\ 2N(1\leq\ i\leq\ N) $ - 入力はすべて整数である ### Sample Explanation 1 $ 4,1,2,3 $ 番目の順に石板を並べたとき、操作の必要回数の期待値は $ 2.25 $ になります。この $ 2^4 $ 倍である $ 36 $ を出力します。