UVa 10692 - Huge Mods

// Theory: a ^ ( b % phi[m]) + phi[m]
// suppose, m=53, n=3, and a1=2, a2=3 and a3=2; then: m=53, m1=phi[m]=52, m2=phi[m1]=24;
// we know: 2 ^ 3 ^ 2 % m ; that means it will be 2 ^ 3 ^ 2 ^ 1
// We have to start from the last, so: ans1 = (2 ^ 1 % m2) + m2=26; which is mod(2 , ans, m2), ans=1 here;
// ans2 = (( 3 ^ ans1) % m1) + m1 = 61; which is mod(3 , ans, m1), ans=ans1;
// main_ans = (2 ^ ans2) % m=35; which is mod(2 , ans, m), ans = ans2;

#include<bits/stdc++.h>
using namespace std;
#define sze 10010
char s[sze];
long phi[sze],vis[sze],i1,j;
void euler_phi()
{
    for(i1=1; i1<=sze; i1++)
        phi[i1]=i1;
    for(i1=2; i1<=sze; i1++)
    {
        if(vis[i1]==0)
        {
            for(j=i1; j<=sze; j+=i1)
            {
                phi[j]=(phi[j]/i1)*(i1-1);
                vis[j]=1;
            }
        }
    }
}
long bigmod(long base,long power,long mod)
{
    if(power==0)
        return 1;
    else if(power%2==0)
    {
        long xx=bigmod(base,power/2,mod);
        return ((xx%mod)*(xx%mod))%mod;
    }
    else
    {
        return ((base%mod)*(bigmod(base,power-1,mod)%mod))%mod;
    }
}
main()
{
    euler_phi();
    long cs=1;
    while(cin>>s)
    {
        if(s[0]=='#')
            break;
        else
        {
            long x=atoi(s),ar[10010]={0},ar1[10010]={0},n,x2,i;
            x2=x;
            cin>>n;
            for(i=1;i<=n;i++)
            {
                cin>>ar[i];
            }
            ar1[1]=x2;
            for(i=2;i<=n;i++)
            {
                x2=phi[x2];
                ar1[i]=x2;
            }
            long ans=1;
            for(i=n;i>=2;i--)
            {
                ans=bigmod(ar[i],ans,ar1[i]);
                ans+=ar1[i];
            }
            ans=bigmod(ar[1],ans,ar1[1]);
            printf("Case #%ld: %ld\n",cs++,ans);
        }
    }
}