Let's define the score of sequence $$A$$ of length $$M$$ the maximal number $$T$$ such that there exist a sequence $$B$$ of length $$T$$ with $$1 = B_1 < B_2 < \dots < B_T \le M$$ and $$B_i$$ is the smallest index bigger than $$B_{i - 1}$$ with $$A_{B_{i - 1}} \le A_{B_{i}}$$.
A sequence $$S$$ of length $$N$$ is randomly generated in the following way:
$$\cdot$$ For each index $$i$$ we assign $$V$$ $$(1 \le V \le K)$$ to $$S_i$$ with probability $$p_V$$.
Find the expected score of $$S$$ modulo $$10^9 + 7$$.
$$\textbf{Input}$$
The first line contains two integers - $$N, K (1 \le N \le 10^9, 1 \le K \le 75)$$.
The next line contains $$K$$ nonegative integers - $$q_1, q_2, \dots, q_k$$, $$p_i = \frac{q_i}{q_1 + q_2 + \dots + q_k}$$ $$(1 \le q_1 + q_2 + \dots + q_k \le 10^9)$$.
$$\textbf{Output}$$
It can be proved that the answer can be represented as a fraction $$\frac{P}{Q}$$ with $$Q \neq 0$$ and $$(P,Q) = 1$$. Output the reminder of $$P \cdot Q ^ {-1}$$ when divided by $$10^9 + 7$$.
3 2 1 2
814814823
Consider the following sequences:
1. $$(1,1,1)$$ appears with probability $$\frac{1}{27}$$ and has score $$3$$
2. $$(1,1,2)$$ appears with probability $$\frac{2}{27}$$ and has score $$3$$
3. $$(1,2,1)$$ appears with probability $$\frac{2}{27}$$ and has score $$2$$
4. $$(1,2,2)$$ appears with probability $$\frac{4}{27}$$ and has score $$3$$
5. $$(2,1,1)$$ appears with probability $$\frac{2}{27}$$ and has score $$1$$
6. $$(2,1,2)$$ appears with probability $$\frac{4}{27}$$ and has score $$2$$
7. $$(2,2,1)$$ appears with probability $$\frac{4}{27}$$ and has score $$2$$
8. $$(2,2,2)$$ appears with probability $$\frac{8}{27}$$ and has score $$3$$
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor