【题目描述】

给出n个正整数a1,a2…an和一个质数mod.一个变量x初始为1.进行m次操作.每次在n个数中随机选一个ai,然后x=x*ai%mod.问m次操作之后x的取值的期望.

答案一定可以表示成a/b的精确分数形式.a和b可能很大,所以只需要输出a*(b^(10^9+5))模10^9+7的结果.

【输入格式】

第一行三个整数n,m,mod.

接下来一行n个空格隔开的正整数a​~1~​,a​~2~​…a~n~~~

【输出格式】

一行一个整数表示答案

【样例输入】

2
1 3 1 2

【样例输出】

3

【数据范围】

第1个测试点:mod=2

第2个测试点:n=1

第3,4,5个测试点:m<=1000,1<=mod<=300.

第6,7,8个测试点: 1<=mod<=300

对于全部测试点: 1<=ai<mod,mod为质数1<=mod<=1000,

对于全部测试点:1<=n<=10^5,1<=m<=10^9

【孙金宁教你学数学】

质数P的原根g满足1<=rt<P,且rt的1次方,2次方…(P-1)次方在模P意义下可以取遍1到(P-1)的所有整数.

欧拉定理:对于质数P,1<=x<P的任意x的P-1次方在模P意义下都为1.

显然,原根的1次方,2次方…（P-2）次方在模P意义下都不为1,只有(P-1)次方在模P意义下为1.这也是一个数成为原根的充分必要条件.