#P7327. 「MCOI-07」Dream and Discs

「MCOI-07」Dream and Discs

题目背景

均匀随机 指对所有可行的结果随机选一个结果,其中所有可行结果等概率被选择。

题目描述

Dream 有 nn 片音乐盘,编号为 11nn。所有盘都存恰好一首歌,其中编号为 ii 的盘所存储歌由正整数 aia_i 表示。aia_i 满足 1ain1\le a_i\le n
Dream 打算均匀随机选择一个编号区间 P1P_1 和一个歌曲区间 S1S_1,其中 P1[1,n]P_1\subseteq [1,n]S1[1,n]S_1\subseteq [1,n],并且所有区间端点均为正整数。
Dream 取完两个区间,他会选择尽量多的盘,使得盘编号在 P1P_1 里,歌曲在 S1S_1 里,并且所有歌曲互不相同。他准备把这集音乐盘给 Tommy。
Dream 构造完集合发现他选了太多音乐盘,决定由以上选区间方法再次均匀随机选取两个区间 P2P_2S2S_2,其中 P2P1P_2\subseteq P_1S2S1S_2\subseteq S_1。这次,他构造的音乐盘集需要满足编号在 P2P_2 里,歌曲在 S2S_2 里。Dream 仍然会选尽量大,歌曲互不相同的集合。
Dream 永远不会选空区间。
现在 Tommy 感觉 Dream 给他的音乐盘太少了。请帮 Tommy 计算 Dream 第二次选取 平均 导致的集合大小减少量。
这里,平均对所有合法 (P1,S1,P2,S2)(P_1,S_1,P_2,S_2) 选取方案等权重平均。

输入格式

第一行一个正整数 nn
第二行 nn 个正整数,依次表示 a1,a2,,ana_1,a_2,\dots,a_n

输出格式

假设答案可以表示为 p/qp/q,其中 ppqq 互质。请输出 pq1(mod109+7)p\cdot q^{-1}\pmod{10^9+7}

2
1 2
920000007
3
1 1 2
480000004
5
1 2 1 3 2
734081639

提示

样例 1 解释

  • P1=[1,1],S1=[1,1]P_1=[1,1],S_1=[1,1]
    • P2=[1,1],S2=[1,1],Δ=11=0P_2=[1,1],S_2=[1,1],\Delta=1-1=0
  • P1=[1,1],S1=[1,2]P_1=[1,1],S_1=[1,2]
    • P2=[1,1],S2=[1,1],Δ=11=0P_2=[1,1],S_2=[1,1],\Delta=1-1=0
    • P2=[1,1],S2=[1,2],Δ=11=0P_2=[1,1],S_2=[1,2],\Delta=1-1=0
    • P2=[1,1],S2=[2,2],Δ=10=1P_2=[1,1],S_2=[2,2],\Delta=1-0=1
  • P1=[1,1],S1=[2,2]P_1=[1,1],S_1=[2,2]
    • P2=[1,1],S2=[2,2],Δ=00=0P_2=[1,1],S_2=[2,2],\Delta=0-0=0
  • P1=[1,2],S1=[1,1]P_1=[1,2],S_1=[1,1]
    • P2=[1,1],S2=[1,1],Δ=11=0P_2=[1,1],S_2=[1,1],\Delta=1-1=0
    • P2=[1,2],S2=[1,1],Δ=11=0P_2=[1,2],S_2=[1,1],\Delta=1-1=0
    • P2=[2,2],S2=[1,1],Δ=10=1P_2=[2,2],S_2=[1,1],\Delta=1-0=1
  • P1=[1,2],S1=[1,2]P_1=[1,2],S_1=[1,2]
    • P2=[1,1],S2=[1,1],Δ=21=1P_2=[1,1],S_2=[1,1],\Delta=2-1=1
    • P2=[1,1],S2=[1,2],Δ=21=1P_2=[1,1],S_2=[1,2],\Delta=2-1=1
    • P2=[1,1],S2=[2,2],Δ=20=2P_2=[1,1],S_2=[2,2],\Delta=2-0=2
    • P2=[1,2],S2=[1,1],Δ=21=1P_2=[1,2],S_2=[1,1],\Delta=2-1=1
    • P2=[1,2],S2=[1,2],Δ=22=0P_2=[1,2],S_2=[1,2],\Delta=2-2=0
    • P2=[1,2],S2=[2,2],Δ=21=1P_2=[1,2],S_2=[2,2],\Delta=2-1=1
    • P2=[2,2],S2=[1,1],Δ=20=2P_2=[2,2],S_2=[1,1],\Delta=2-0=2
    • P2=[2,2],S2=[1,2],Δ=21=1P_2=[2,2],S_2=[1,2],\Delta=2-1=1
    • P2=[2,2],S2=[2,2],Δ=21=1P_2=[2,2],S_2=[2,2],\Delta=2-1=1
  • P1=[1,2],S1=[2,2]P_1=[1,2],S_1=[2,2]
    • P2=[1,1],S2=[2,2],Δ=10=1P_2=[1,1],S_2=[2,2],\Delta=1-0=1
    • P2=[1,2],S2=[2,2],Δ=11=0P_2=[1,2],S_2=[2,2],\Delta=1-1=0
    • P2=[2,2],S2=[2,2],Δ=11=0P_2=[2,2],S_2=[2,2],\Delta=1-1=0
  • P1=[2,2],S1=[1,1]P_1=[2,2],S_1=[1,1]
    • P2=[2,2],S2=[1,1],Δ=00=0P_2=[2,2],S_2=[1,1],\Delta=0-0=0
  • P1=[2,2],S1=[1,2]P_1=[2,2],S_1=[1,2]
    • P2=[2,2],S2=[1,1],Δ=10=1P_2=[2,2],S_2=[1,1],\Delta=1-0=1
    • P2=[2,2],S2=[1,2],Δ=11=0P_2=[2,2],S_2=[1,2],\Delta=1-1=0
    • P2=[2,2],S2=[2,2],Δ=11=0P_2=[2,2],S_2=[2,2],\Delta=1-1=0
  • P1=[2,2],S1=[2,2]P_1=[2,2],S_1=[2,2]
    • P2=[2,2],S2=[2,2],Δ=11=0P_2=[2,2],S_2=[2,2],\Delta=1-1=0

总共有 2525 方案,所有方案减量之和为 1414,于是答案等于 14/2514/25

样例 2 解释

答案为 144/225144/225

样例 3 解释

答案为 5921/49005921/4900

数据规模与约定

本题采用捆绑测试。

  • Subtask 1(11 pts):n8n\le8
  • Subtask 2(17 pts):n64n\le64
  • Subtask 3(19 pts):n1024n\le1024
  • Subtask 4(7 pts):ai10a_i\le 10
  • Subtask 5(23 pts):n105n\le10^5
  • Subtask 6(23 pts):无特殊限制。

对于所有数据,1n5105,1ain1\le n\le5\cdot10^5,1\le a_i\le n