Niuniu likes to play OSU! We simplify the game OSU to the following problem. Given n and m, there are n clicks. Each click may success or fail. For a continuous success sequence with length X, the player can score X^m. The probability that the i-th click success is p[i]100. We want to know the expectation of score. As the result might be very large (and not integral), you only need to output the result mod 1000000007.
输入描述:
The first line contains two integers, which are n and m.The second line contains n integers. The i-th integer is p[i].1 1 0 = p[i] = 100
输出描述:
You should output an integer, which is the answer.
示例1
说明
000 0
001 1
010 1
011 16
100 1
101 2
110 16
111 81
The exact answer is (0 + 1 + 1 + 16 + 1 + 2 + 16 + 81) / 8 = 59/4.
As 750000020 * 4 mod 1000000007 = 59
You should output 750000020.
备注:
If you don't know how to output a fraction mod 1000000007,You may have a look at https:en.wikipedia.orgwikiModular_multiplicative_inverse
加载中...