记录编号	421458	评测结果	AAAATAAAAAAAAAAAATTA
题目名称	MikeNOI	最终得分	85
用户昵称	Imone NOI2018Au	是否通过	未通过
代码语言	C++	运行时间	8.316 s
提交时间	2017-07-06 21:56:58	内存使用	13.44 MiB

#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define MAXN 100010
#define MAXF 262144
#define LOGN 30
#define ll long long
#define ld long double
#define func inline __attribute((optimize("Ofast")))
#define mul(x, y) (((ll)(x) * (ll)(y)) % MOD)
using namespace std;

const ld PI = acos(-1.0);
const int MOD = 99991;

void Read(int& x){
	char ch;
	while(ch=getchar(), ch<'0'||ch>'9');
	x = ch - '0';
	while(ch=getchar(), ch>='0'&&ch<='9') x = x * 10 + ch - '0';
}

struct virt {
	ld r, i;
	inline virt operator+(virt x) {
		return {r+x.r, i+x.i};
	}
	inline virt operator-(virt x) {
		return {r-x.r, i-x.i};
	}
	inline virt operator*(virt x) {
		return {r * x.r - i * x.i, r * x.i + i * x.r};
	}
};

virt W[LOGN][2];

func void rader(virt A[], int n) {
	int i, j = n >> 1;
	for(i=1;i<n-1;i++) {
		if(i < j) swap(A[i], A[j]);

		int k = n >> 1;
		while(j >= k) {
			j -= k;
			k >>= 1;
		}
		if(j < k) j += k;
	}
}

func void fft(virt A[], int n, int on) {
	int i, h, logh, k;
	rader(A, n);
	for(h=2,logh=1;h<=n;h<<=1,logh++) {
		virt wn = W[logh][on];
		for(i=0;i<n;i+=h) {
			virt w = {1, 0};
			for(k=i;k<i+h/2;k++) {
				virt u = A[k];
				virt t = A[k + h / 2] * w;
				A[k] = u + t;
				A[k + h / 2] = u - t;
				w = w * wn;
			}
		}
	}
	if(on == 1) for(i=0;i<n;i++) A[i].r /= n;
}

func void conv(virt A[], virt B[], virt R[], int n) {
	int i;
	fft(A, n, 0); fft(B, n, 0);
	for(i=0;i<n;i++) R[i] = A[i] * B[i];
	fft(R, n, 1);
}

int A[MAXN], P[MOD], N, K;
int X[MAXN];

virt Va[MAXF], Vb[MAXF];
func void solve(int l, int r) {
	if(l == r) X[l] = P[A[l]];
	else {
		int i, n, nl, nr, nm, m = (l+r) / 2;
		solve(l, m); solve(m+1, r);

		nl = m - l + 1; nr = r - m; nm = (r - l + 1) << 1;
		for(n=1;n<nm;n<<=1);

		Va[0] = {1, 0};
		for(i=1;i<=nl;i++) Va[i] = {X[l+i-1], 0};
		for(i=nl+1;i<n;i++) Va[i] = {0, 0};

		Vb[0] = {1, 0};
		for(i=1;i<=nr;i++) Vb[i] = {X[m+1+i-1], 0};
		for(i=nr+1;i<n;i++) Vb[i] = {0, 0};

		conv(Va, Vb, Va, n);
		for(i=l;i<=r;i++) X[i] = ((ll)round(Va[i-l+1].r)) % MOD;
	}
}

int Ans = 0;

int main() {
	freopen("MikeNOI.in", "rt", stdin);
	freopen("MikeNOI.out", "wt", stdout);
	
	int i, k; int f0, f1, MA, MB, EA, EB;

	for(i=2;i<LOGN;i++) for(k=0;k<=1;k++) {
		int on = k ? -1 : 1;
		W[i][k] = {cos(-on*2*PI/(1<<i)), sin(-on*2*PI/(1<<i))};
	}

	Read(N); Read(K);
	for(i=0;i<N;i++) Read(A[i]), A[i] %= (MOD - 1);
	Read(f0); Read(f1);

	MB = mul(f0 + f1, 24998);

	P[0] = 1;
	for(i = 1; i < MOD; i++) P[i] = (3 * P[i-1]) % MOD;
	Ans = mul(MB, (solve(0, N-1), X[K - 1]));

	MA = (f0 - MB) % MOD;

	P[0] = 1;
	for(i = 1; i < MOD; i++) P[i] = -P[i-1] % MOD;
	Ans = (Ans + mul(MA, (solve(0, N-1), X[K - 1]))) % MOD;

	printf("%d", (Ans + MOD) % MOD);
}