指数循环节,由于a ^x = a ^(x % m + phi(m)) (mod m)仅在x >= phi(m)时成立,故应注意要判断
//by:Gavin http://www.cnblogs.com/IMGavin/
//指数循环节 递归处理
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
using namespace std;
typedef long long LL;
const int N = 10008, INF = 0x3F3F3F3F;
LL a[N], mod, n;
int phi[N];
void allPhi(int n){
memset(phi,0,sizeof(phi));
phi[1]=1;
for(int i=2;i<=n;i++){
if(!phi[i]){//则i为素数
phi[i]=i;
for(int j=i;j<=n;j+=i){
if(!phi[j]){
phi[j]=j;
}
phi[j]=phi[j]/i*(i-1);
}
}
}
}
LL PowMod(LL a,LL b,LL MOD){
LL ret=1;
while(b){
if(b&1){
ret = ret * a % MOD;
}
a = a * a % MOD;
b>>=1;
}
return ret;
} bool check(LL a, LL n, LL m){
if(a == 1){
return false;
}
LL ans = 1;
for(int i = 0; i < n; i++){
ans *= a;
if(ans >= m){
return true;
}
}
return false;
} LL dfs(LL d, LL m, bool &sym){
if(d == n){
if(a[d] >= m){
sym = 1;
}else{
sym = 0;
}
return a[d] % m;
}
bool flag;
LL p = dfs(d + 1, phi[m], flag);
if(flag){
p += phi[m];
}
sym = check(a[d], p, m);
return PowMod(a[d], p, m);
} int main(){
allPhi(N - 2);
int t = 0;
while(cin >> mod){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
bool flag;
printf("Case #%d: %lld\n", ++t, dfs(1, mod, flag) % mod);
}
return 0;
}