#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define MAXN 5000
using namespace std;

long long g[MAXN][MAXN];
long long f[MAXN];
long long F[MAXN];

int main(){
	int T;
	cin>>T;
	while(T--){
		int n,MM;
		scanf("%d%d",&n,&MM);
		F[1]=1;
		F[2]=2;
		rep(i,3,n)
			F[i]=(F[i-1]+F[i-2])%MM;
		g[1][1]=1;
		g[1][2]=0;
		rep(i,2,n){
			g[i][1]=(g[i-1][1]+F[i])%MM;
			rep(j,2,i)
				g[i][j]=(g[i-1][j]+F[i]*g[i-1][j-1])%MM;
			g[i][i+1]=0;
		}
		long long ans=0;
		rep(i,1,n)
			scanf("%I64d",&f[i]);
		rep(i,1,n)
			if (i&1)
				ans=(ans+g[n][i]*f[n+1-i])%MM;
			else
				ans=(ans-g[n][i]*f[n+1-i])%MM;
		printf("%I64d\n",(ans%MM+MM)%MM);
	}
}