Expected Product

All submissions for this problem are available.
### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK108/hindi/EXPTPROD.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK108/mandarin/EXPTPROD.pdf), [Russian](http://www.codechef.com/download/translated/COOK108/russian/EXPTPROD.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK108/vietnamese/EXPTPROD.pdf), and [Bengali](http://www.codechef.com/download/translated/COOK108/bengali/EXPTPROD.pdf) as well. Chef is playing a tricky game with a sequence $a_1, a_2, \ldots, a_N$. Initially, his score is $S = 1$. In the game, he performs the following process exactly $K$ times (note that the sequence $a$ never changes):  Pick an element $X$ from the sequence $a$ uniformly randomly.  Change the score $S$ to $(S \cdot X) \% N$. Find the expected value of Chef's score $S$ at the end of the game. It can be shown that this expected value can be expressed as a fraction $\frac{P}{Q}$, where $P$ and $Q$ are coprime integers, $P \ge 0$, $Q \gt 0$ and $Q$ is coprime with $10^9 + 7$. You should compute $P \cdot Q^{1} \% (10^9 + 7)$, where $Q^{1}$ denotes the multiplicative inverse of $Q$ modulo $10^9+7$. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains two spaceseparated integers $N$ and $K$.  The second line contains $N$ spaceseparated integers $a_1, a_2, \ldots, a_N$. ### Output For each test case, print a single line containing one integer $P \cdot Q^{1}$ modulo $10^9 + 7$. ### Constraints  $1 \le T \le 5$  $2 \le N \le 1,000$  $0 \le a_i \lt N$ for each valid $i$  $1 \le K \le 10^9$ ### Example Input ``` 2 2 3 1 1 3 2 2 1 2 ``` ### Example Output ``` 1 444444449 ``` ### Explanation **Example case 1:** Regardless of Chef's exact choices, the final score is always $(1 \cdot 1 \cdot 1) \% 2 = 1$.Author:  imanik 
Editorial  https://discuss.codechef.com/problems/EXPTPROD 
Tags  cook108, expectedvalue, exponentiation, imanik, taran_1407 
Date Added:  12072019 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions