You are given k polynomials of degree n each and coefficient 1 for each of the powers i.e the polynomial is of the type : 1+xid+x2id+−−−−−−−−+xnid where id denotes what variable we are using for expressing the polynomial.
Note: id here is used to distinguish the variables of any two polynomials)
Now you are given k such polynomials with same or different id's and you have to multiply all of them. After multiplication you need to group them so that there are no two similar variable product terms.
Now you are given an integer i and you have to tell the expected value of the power of variable with id i in the term if you pick any term at random from the new polynomial formed out of multiplication of the given k polynomials.
Note : Please see the sample input output for more clarification
Input
First line contains two numbers n and k as input where n is the degree of the polynomials and k is the count of the polynomials.
Next k lines contain id's that denote the ith polynomial's id. Last line contains the number i as input
Output
In the output you have to print the expected value of the expression asked. If your answer is of the form P/Q then you have to print (P×Q−1) mod 109+7 where Q−1 is the modular multiplicative inverse of Q with respect to 109+7
The given value of id's in the sample is 1 , 2 and 1 so we have the polynomials 1+x1,1+x2,1+x1 which on multiplication gives us 1+x2+x1+x2+x1+x1×x2+x21+x1×x2 . On grouping the terms with same variables, we get 1+x21+2×x1+x2+x21×x2+2×x1×x2.
Now if we pick each term at random and find the expected value, then we will get -
0∗(1/6)+0∗(1/6)+0∗(1/6)+1∗(1/6)+1∗(1/6)+1∗(1/6)=1/2
So the answer is 1∗2−1=500000004
