最长不下降子序列

题目描述 𝑝𝑝𝑖𝑖 1000−𝑝𝑝𝑖𝑖 有一个随机的01序列𝑎𝑎1 , 𝑎𝑎2 , … 𝑎𝑎𝑛𝑛 。其中第𝑖𝑖位有 的概率为1，有 的概率为0。 1000 1000

问这个01序列的最长不下降子序列的长度期望是多少，设这个值为𝐸𝐸，输出 𝐸𝐸 × 1000𝑛𝑛 模109 + 7的结果。

输入格式 第一行一个整数𝑛𝑛。

接下来一行𝑛𝑛个整数𝑝𝑝1 , 𝑝𝑝2 , … , 𝑝𝑝𝑛𝑛 。

输出格式 一个整数，表示答案。

样例输入 1 3 400 500 600

样例输出 1 599999986

样例输入输出 2 见下发文件。

数据规模 共 10 个测试点。

测试点1,2,3满足𝑛𝑛 ≤ 15。

测试点4,5,6满足𝑛𝑛 ≤ 50。

对于所有数据，满足1 ≤ 𝑛𝑛 ≤ 200,0 ≤ 𝑝𝑝𝑖𝑖 ≤ 1000。