It's the beginning of a new relationship. Will this one result in joy or sorrow? In LoveChoice, you choose the actions that determine how the relationship unfolds. Pick your responses to each of the situations. These endearing and bittersweet stories are surprisingly realistic and easy to relate to.
To win Eva's heart, Colin studies hard by playing LoveChoice on Steam. To simplify the problem, we describe it as follows:
There are $$$n$$$ multiple-choice questions; the $$$i$$$-th question has $$$a_i$$$ normal choices. Additionally, some questions have an alternative hidden choice. There is only one correct choice for each question, and if a hidden choice exists, it must be the correct choice.
In a round of the game, you must answer all the questions in order. After answering all the questions, the system will tell you if each question is answered correctly.
Colin is calm. For each question, he will only choose one of the choices that may not be the wrong choice, with equal probability each time. However, Colin's observation ability is relatively ordinary, so if a question $$$i$$$ has a hidden choice, Colin will not be aware of its existence before knowing that all the $$$a_i$$$ normal choices for this question are wrong.
Colin is hardworking. His goal is to answer all questions correctly in a round. Please calculate the expected number of rounds for him to answer all the questions correctly for the first time.
The first line has two integers $$$n,m ~(1\le m\le n\le 5\times 10^3)$$$, representing that there are $$$n$$$ questions in the game and that there are $$$m$$$ questions that have a hidden choice.
The second line has $$$n$$$ integers $$$a_1, a_2, \dots, a_n~(1\le a_i\le 10^9)$$$ , representing that there are $$$a_i$$$ normal choices for the $$$i$$$-th question.
The third line has $$$m$$$ distinct integers $$$b_1, b_2,\dots, b_m~(1\le b_i\le n)$$$ , representing that the $$$b_i$$$-th question has a hidden choice.
Output a single integer, representing the expected number of rounds for him to answer all the questions correctly for the first time, modulo $$$10^9+7$$$.
2 1 1 3 1
333333338
In the example, there are $$$2$$$ questions with $$$1$$$ choice and $$$3$$$ choices, respectively, and question $$$1$$$ has a hidden choice. Thus, Colin cannot answer the first question correctly in the first round, as he does not know the existence of the hidden choice in the first round.
The probability of answering all the questions correctly for the first time in the second round is $$$\frac {2}{3}$$$.
The probability of answering all the questions correctly for the first time in the third round is $$$\frac{1}{3}$$$.
So the answer to the example is $$$\frac{2}{3} \times 2 + \frac{1}{3} \times 3 = \frac{7}{3}$$$ , which modulo $$$10^9+7$$$ is $$$333333338$$$.
