3756: 我是 B 题(第六轮01)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
有 n 个质量分别为 1 ~ n 的物品需要经过 n − 1 道质检工序。
每一轮工序会收到上一轮传过来的所有物品并开始质检，第 i 道工序流程如下：
- 如果此时该道工序处只剩下一个物品，那么机器会将其粉碎。
- 如果此时该道工序处剩下了不止一个物品，那么机器会将质量最小的物品挑出 来，以 pi 的概率将其粉碎， 1 − pi 的概率放过它并将其传给下一道工序。如果 机器放过了本次选择的物品，那么重新执行该流程直到粉碎某一个物品。
求最后剩下的物品质量的期望，答案对 109 + 7取模。
输入
第一行一个正整数 n。
第二行 n − 1 个正整数 pi，含义见题面。
输出
一个整数表示答案。
样例输入 复制
10
3122 53425 1234214 653455 32412 1234 2432 3421 3543132样例输出 复制
136795160提示
对于 25% 的数据， n ≤ 10。 对于 55% 的数据， n ≤ 20。
对于 70% 的数据， n ≤ 100。
对于另外 5% 的数据， pi ∈ {0,1}。
对于另外 10% 的数据， pi = 500000004。
对于 100% 的数据， n ≤ 300,0 ≤ pi < 10^9 + 7。