Fantasy of a Summation n个数，k层重复遍历相加。求它的和%mod的值；推导公式+快速幂

/**
题目：Fantasy of a Summation 
链接：https://vjudge.net/contest/154246#problem/L
题意：n个数，k层重复遍历相加。求它的和%mod的值；
思路：很容易想到n个数出现在要加的和中的次数相同。
又所有数的出现次数为n^k * k:
所以每个数出现的次数为n^k * k / n;
*/

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn = 1004;
int mod;
int a[maxn];
int n, k;
ll solve(ll a,ll b)
{
    ll p = 1;
    while(b>0){
        if(b&1) p = p*a%mod;
        a = a*a%mod;
        b >>= 1;
    }
    return p;
}
int main()
{
    int T, cas=1;
    cin>>T;
    while(T--)
    {
        scanf("%d%d%d",&n,&k,&mod);
        for(int i = 0; i < n; i++) scanf("%d",&a[i]);
        ll sum = 0;
        for(int i = 0; i < n; i++) sum += a[i];
        sum%=mod;
        printf("Case %d: %lld
",cas++,solve(n,k-1)*k%mod*sum%mod);

    }
    return 0;
}