配点 : 800 点
問題文
--收集散落在世界各地的石碑。给混乱带来秩序。再见,我无法给你任何光明……
高桥在解谜角色扮演游戏《蛇核世界的混沌》中的发挥现在已经达到了高潮。
这款游戏的背景是一个遥远的过去,魔法文明繁荣的帝国。一千二百年前,在皇帝的恐怖统治下,公民通过政变夺取了权力。 他们决定将作为帝王力量源泉的神牌分散到各地,以防止将来再出现这样的强者。但讽刺的是,正是这件事 以魔力为基础的国家统一被打破,中央和地方都被肆意破坏,放置石碑的地方也被遗忘。
主角是一个梦想复兴富裕的魔法帝国的男孩。这个男孩在高桥君的控制下,走遍了全国各地的村庄、森林、洞穴,最终收集了所有的石碑。
全石碑 N 可用,i 石板表是一个整数。 A_i 但是后面是一个整数 写入 B_i 。
现在少年已经回到了古都,他要做的就是将废墟宫殿最深处的平台上的石碑排列起来。但这是最后的也是最大的困难。
石碑可以水平排列在支架上。男孩可以将石碑以任何顺序排列在桌子上,任何一面朝上。当男孩把所有的石碑都摆好后, 建立政府的公民施下的古老诅咒可以被激活,将石碑翻过来。石碑无论在什么位置,都有恰好一半的几率被掀翻。
然后男孩可以根据需要多次交换相邻的石板。如果男孩能够排列石碑,使得写在上面的整数从左边单调递增,那么 人民安居乐业的帝国得到了复兴,男孩的梦想也实现了。不过,如果这个操作花费太多时间的话……古老的魔法就会被激活,石板就会再次散落!
一旦药片散落,男孩必须再次收集它们。高桥先生想要快速通关游戏,因此交换相邻石碑所需的操作次数的期望值为 我决定把石碑放在一个架子上,使它们成为最小的。
高桥君玩游戏太多了,眼睛越来越累了。对于高桥君来说,所需操作次数的最小期望值为 2^N 乘以该值(该值可以证明是一个整数) 除以 10^9+7 后求余数。
制約
- 1\leq N\leq 10^5
- 1\leq A_i,B_i\leq 2N(1\leq i\leq N)
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N A_1 B_1 : A_N B_N
出力
所需操作次数的最小预期值。 2^N 次 打印除以 10^9+7 后的余数。 当石碑按
入力例 1
4 1 5 2 6 8 2 3 4
出力例 1
36
4,1,2,3 顺序排列时,预期操作次数为 2.25 。这个 2^4 次 输出 36 。
入力例 2
6 3 8 10 2 1 5 9 9 12 7 2 4
出力例 2
224