FIICode 2024 Open | Losing Streak

$\mathbb{NUME}$ is a big fan of the popular MOBA League of Legends. He just got off work and plans to play $n$ games of LOL. The only problem is that he is afraid of losing streaks. He knows that if he loses too many games in a row, his night will be ruined. Fortunately, by methods only known to him, he knows for each game what is the chance that he will lose it. Given this information, he wants to know what is the expected value of the length of the longest losing streak during those $n$ games. The answer should be given modulo $10^9 + 7$.

Input

The first line contains an integer $n$ ($1 \le n \le 5\,000$) – the number of games that $\mathbb{NUME}$ will play.

The second line contains $n$ integers $p_i$ ($0 \le p_i \le 100$) – the percent probability that $\mathbb{NUME}$ will lose the $i$-th game.

Output

You should output one number – the expected value of the length of the longest losing streak modulo $10^9 + 7$.

Example 1

stdin

2
50 50

stdout

1

Example 2

stdin

9
50 3 19 83 24 24 94 26 83

stdout

575309567

Notes

In the first example we have a $50\%$ chance of losing each game. Therefore, we have a $1 / 4$ chance of losing both games, $1 / 2$ chance of winning only one game, and $1 / 4$ of winning both games.

So in the end the answer is $0 \cdot (1 / 4) + 1 \cdot (1 / 2) + 2 \cdot (1 / 4) = 1$.