#include<bits/stdc++.h>
using namespace std;
const int mod=1e7+29;
int n,m,a[5];
int qpow(int a,int b){
	if(b==1) return a;
	int p=qpow(a,b>>1);
	if(b&1) return p*p%mod*a%mod;
	return p*p%mod;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	if(n==1) printf("%d",qpow(a[1],m));
	else if(n==2){
		int data=sqrt(a[1]*a[1]-4*a[2]);
		int x=(data-a[1])/2,y=-(data+a[1])/2;
		printf("%d",(qpow(x,m)+qpow(y,m))%mod);
	}
	return 0;
}