#P17945. Senren Banka
Senren Banka
Senren Banka
一个游戏有 道选择关卡。每一轮从第 关开始,答对第 关后才能继续第 关。任意一关答错,该轮立即结束,下一轮重新从第 关开始。某一轮连续答对全部 关后,游戏首次通关。
AI 会根据过去的尝试学习:第 次尝试第 关时,答对的概率为 。各关的尝试次数独立累计,失败重开一轮不会清空计数。
求首次通关所需轮数的期望,对 取模。
输入格式
本题只有一组数据。
第一行包含两个整数 ,,。
接下来 行,每行 个整数 ,满足 ,实际概率为
不保证这些概率随尝试次数单调。
输出格式
输出一个整数,表示所求期望对 取模的结果。分数按分母的模逆元解释。
样例 1
1 1
50
2
样例 2
2 2
25 50
50 25
499122183
样例 3
10 10
1 2 3 4 5 6 8 7 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
473598335