#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
const int N = 5000010;
int n, p, k;
int fact[N], a[N], infact[N],mi[N];
int ans;
int qmi(int a, int k, int p)
{
	int res = 1;
	while (k)
	{
		if (k & 1) res = (long long)res * a % p;
		k >>= 1;
		a = (long long)a * a % p;
	}
	return res;

}
int main()
{
	scanf("%d%d%d", &n, &p, &k);

	fact[0] = infact[0] = a[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		fact[i] = (long long)fact[i - 1] * a[i] % p;
	}
	
	infact[n] = qmi(fact[n], p - 2, p);
	for (int i = n-1; i >= 1; i--)
	{
		infact[i] = (long long)infact[i + 1] * a[i + 1]%p;
	}

	for (int i = 1,j=k; i <= n; i++,j=(long long)j*k%p)
	{
		ans += (long long)j * infact[i] % p * fact[i - 1] % p;
		ans %= p;
	}
	cout << ans << endl;
	return 0;
}

我的想法是，处理出前缀积fact[n]和前缀积的逆元infact[n]，这样就能很容易的得出ai的逆元ai^-1=infact[i]*fact[i-1]。然后根据题目要求求和就是答案了。 对于逆元，我们只需要用快速幂求出infact[n]，然后再用递推公式infact[i-1]=infact[i]*a[i]就能够求出剩余的逆元，这样所有的时间复杂度都应该是O(n)的，不知道为什么会超时