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 <= n <= 1000
1 <= m <= 1000
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.org/wiki/Modular_multiplicative_inverse