#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long a[10];
int main() {
	cin>>n>>m;
	for(long long i=1; i<=n; i++) {
		cin>>a[i];
	}
	if(n==2) {
		long long c;
		c=a[1]*a[1];
		long long b;
		b=c-4*a[2];
		b=sqrt(b);
		c=a[1];
		a[1]=(c+b)/2;
		a[2]=(c-b)/2;
	}
	long long s=0;
	for(long long i=1; i<=n; i++) {
		long long z=a[i];
		for(long long j=1; j<m; j++) {
			a[i]*=z;
			a[i]%=10000029;
		}
		s=s+a[i];
		s=s% 10000029;
	}
	cout<<s;
}
谢谢。