AC 前三个点，TLE 后面两个点。卡不动了，求帮忙卡常。

（本来想去 LOJ 上交一发的，但 LOJ 炸了）

#include <bits/stdc++.h>
using namespace std;
#define int long long
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar()

            ;
    }
    return x * f;
}

const int MAXN = 5e6 + 5;
int n, p, k, a[MAXN], sv[MAXN], s[MAXN], ans;

int quickpow(int x, int y)
{
    int ret = 1, base = x;
    while (y)
    {
        if (y & 1)
        {
            ret *= base;
            ret %= p;
        }
        base *= base;
        base %= p;
        y >>= 1;
    }
    return ret;
}

signed main(void)
{
    n = read(), p = read(), k = read();
    for (int i = 0; i < n; i++)
    {
        a[i] = read();
    }
    s[0] = a[0];
    for (int i = 1; i < n; i++)
    {
        s[i] = s[i - 1] * a[i] % p;
    }
    sv[n - 1] = quickpow(s[n - 1], p - 2);
    for (int i = n - 2; i >= 0; i--)
    {
        sv[i] = sv[i + 1] * a[i + 1] % p;
    }
    for (int i = 0; i < n; i++)
    {
        if (i == 0)
        {
            ans += (quickpow(k, i + 1) % p * sv[i]) % p;
            ans %= p;
            continue;
        }
        // cout << "ny of a[" << i << "] is" << (sv[i] * s[i - 1]) % p << endl;
        ans += (quickpow(k, i + 1) % p * (sv[i] % p * s[i - 1] % p)) % p;
        ans %= p;
    }
    printf("%lld",ans);
    return 0;
}