AT_colopl2018_final_d Chaos of the Snuke World

*——收 集 散 落 天 涯 的 石 板，给 混 乱 带 来 秩 序。最 终，光 明 将 降 临——* 高桥君正在玩的解谜 RPG「Chaos of the Snuke World」迎来了最高潮。 故事发生在一个曾经魔法文明高度发达的古老帝国。大约一千二百年前，居民发动了一场推翻实行恐怖统治的皇帝的政变，并夺得了政权。为了防止这样的统治者再次出现，他们决定将作为皇帝力量来源的魔法石板分散到各地。讽刺的是，这一措施导致国家因失去魔力而分崩离析，中央与地方都陷入了毁灭，而人们逐渐遗忘了石板的存在。 主人公是一位少年，他梦想着重建这个昔日繁荣的魔法帝国。在高桥君的操作下，这位少年走遍村庄、森林和洞穴，终于集齐了所有石板。 **总共有 $N$ 块石板，每块石板正面写着整数 $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)$ - 所有输入均为整数 ### 示例解释 按 $4,1,2,3$ 顺序排列石板时，操作次数的期望值为 $2.25$。因此，输出其 $2^4$ 倍，即 $36$。 **本翻译由 AI 自动生成**