#include<stdio.h>
#include<math.h>
#include <iostream>
int main(){
int d;
int n;
int x;
scanf("%d", &d);
for(int i = 0; i < d; ++i){
scanf("%d", &n);
int t[n];
for(int j=0;j<n+1;j++)
std::cin>>t[j];
scanf("%d", &x);
int i;
int w = 0;
for(int k=0; k<=n; k++){
w *= x;
w += t[k];
}
if(i!=(d-1))
printf("%d\n",w%1243);
else
printf("%d ppp",w%1243);
}
return 0;
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8bWF0aC5oPgojaW5jbHVkZSA8aW9zdHJlYW0+CgppbnQgbWFpbigpewoKICAgIGludCBkOwogICAgaW50IG47CiAgICBpbnQgeDsKCiAgICBzY2FuZigiJWQiLCAmZCk7CiAgICBmb3IoaW50IGkgPSAwOyBpIDwgZDsgKytpKXsKCXNjYW5mKCIlZCIsICZuKTsKCQoJaW50IHRbbl07CgoJZm9yKGludCBqPTA7ajxuKzE7aisrKQoJCXN0ZDo6Y2luPj50W2pdOwoKCXNjYW5mKCIlZCIsICZ4KTsKCiAgICAJaW50IGk7CiAgICAJaW50IHcgPSAwOwoKICAgIAlmb3IoaW50IGs9MDsgazw9bjsgaysrKXsKCQl3ICo9IHg7CgkJdyArPSB0W2tdOwoJfQoKCWlmKGkhPShkLTEpKQoJCXByaW50ZigiJWRcbiIsdyUxMjQzKTsKCWVsc2UKCQlwcmludGYoIiVkIHBwcCIsdyUxMjQzKTsKfQogICAgcmV0dXJuIDA7Cn0=