WA 0pts

#include <bits/stdc++.h>
using namespace std;
#define int long long
int cs,n,mod,a[20];
inline int qp(int a,int b,int c,int ret=1) {
	bool flag=1.0*log(c)/log(a)<=1.0*b;
	while(b) {if(b&1) ret=ret*a%c;a=a*a%c,b>>=1;}
	return ret+flag*c;
}
inline int phi(int a) {
	int ret=a;
	for(int i=2;i*i<=a;++i)
		if(a%i==0) {
			ret=ret/i*(i-1);
			while(a%i==0) a/=i;
		}
	if(a>1) ret=ret/a*(a-1);
	return ret;
}
int work(int p,int i) {
	if(i==n) return a[n]%p+(a[n]<p?0:p);
	return qp(a[i],work(phi(p),i+1),p);
}
signed main () {
	while(cin>>mod) {
		if(mod=='#') break;
		cin>>n;
		for(int i=1;i<=n;++i) cin>>a[i];
		printf("Case #%d: %d\n",++cs,work(mod,1)%mod);
	}
	return 0;
}