← 返回题目列表

AtCoder · arc104_e

E. 随机 LIS

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

给定的是长度的整数序列 N: A_1, A_2, \cdots, A_N.

整数序列 X,其长度也是 N,将通过独立选择的方式随机选择 X_i 来自整数的均匀分布 1, 2, \ldots, A_i 对于每个 i (1 \leq i \leq N).

计算该序列的最长递增子序列的长度期望值 X,模数 1000000007.

更正式地说,在问题的约束下,我们可以证明期望值可以表示为有理数,即不可约分数 \frac{P}{Q},并且唯一存在一个整数 R 这样 R \times Q \equiv P \pmod {1000000007} 和 0 \leq R < 1000000007,所以打印这个整数 R.

注释

序列的子序列 X 是通过提取部分元素得到的序列 X 并在不改变顺序的情况下排列它们。序列的最长递增子序列 X 是严格递增子序列中长度最大的序列 X.

约束

  • 1 \leq N \leq 6
  • 1 \leq A_i \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \cdots A_N

输出

打印期望值模 1000000007.


示例输入 1

3
1 2 3

示例输出 1

2

X 成为以下之一,有概率 1/6 对于每个:

  • X = (1,1,1),其中最长递增子序列的长度为 1;
  • X = (1,1,2),其中最长递增子序列的长度为 2;
  • X = (1,1,3),其中最长递增子序列的长度为 2;
  • X = (1,2,1),其中最长递增子序列的长度为 2;
  • X = (1,2,2),其中最长递增子序列的长度为 2;
  • X = (1,2,3),其中最长递增子序列的长度为 3.

因此,最长递增子序列的长度期望值为 (1 + 2 + 2 + 2 + 2 + 3) / 6 \equiv 2 \pmod {1000000007}.


示例输入 2

3
2 1 2

示例输出 2

500000005

X 成为以下之一,有概率 1/4 对于每个:

  • X = (1,1,1),其中最长递增子序列的长度为 1;
  • X = (1,1,2),其中最长递增子序列的长度为 2;
  • X = (2,1,1),其中最长递增子序列的长度为 1;
  • X = (2,1,2),其中最长递增子序列的长度为 2.

因此,最长递增子序列的长度期望值为 (1 + 2 + 1 + 2) / 4 = 3 / 2。自从 2 \times 500000005 \equiv 3 \pmod {1000000007},我们应该打印 500000005.


示例输入 3

6
8 6 5 10 9 14

示例输出 3

959563502