#include    
#include    
#include    
#define LL long long   
  
LL a[20];  
  
LL euler(LL n)  
{  
    LL m=(LL)sqrt(n+0.5);  
    LL ans=n;  
    for(LL i=2;i<=m;i++)  
    if(n%i==0){  
        ans=ans/i*(i-1);  
        while(n%i==0)n/=i;  
    }  
    if(n>1)ans=ans/n*(n-1);  
    return ans;  
}  
  
LL pmod(LL a,LL n,LL m)  
{  
    LL now = 1;  
    for(LL i=0;i=m)  break;  
    }  
    if(now >= m)   now = m;  
    else now=0;  
  
    if(n==0)return 1;  
    LL x=pmod(a,n/2,m);  
    LL ans=(LL)x*x%m;  
    if(n%2==1) ans=ans*a%m;  
    return ans+now;  
}  
  
LL solve(LL cur,LL n,LL m)  
{  
    if(cur==n-1)  
    {  
        if(a[cur]>=m)  
        return a[cur]%m+m;  
        else  
        return a[cur];  
    }  
    LL M=euler(m);  
    LL p=solve(cur+1,n,M);  
    LL ans=pmod(a[cur],p,m);  
    return ans;  
}  
  
int main()  
{  
    char s[10];  
    LL m,n;  
    int cas=0;  
    while(scanf("%s",s)==1)  
    {  
        int l=strlen(s);  
        if(s[0]=='#'&&l==1)break;  
        m=0;  
        for(int i=0;i
#include 
#include 
#define LL long long

LL a[20];

LL euler(LL n)
{
    LL m=(LL)sqrt(n+0.5);
    LL ans=n;
    for(LL i=2;i<=m;i++)
    if(n%i==0){
        ans=ans/i*(i-1);
        while(n%i==0)n/=i;
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}

LL pmod(LL a,LL n,LL m)
{
    LL now = 1;
    for(LL i=0;i=m)  break;
    }
    if(now >= m)   now = m;
    else now=0;

    if(n==0)return 1;
    LL x=pmod(a,n/2,m);
    LL ans=(LL)x*x%m;
    if(n%2==1) ans=ans*a%m;
    return ans+now;
}

LL solve(LL cur,LL n,LL m)
{
    if(cur==n-1)
    {
        if(a[cur]>=m)
        return a[cur]%m+m;
        else
        return a[cur];
    }
    LL M=euler(m);
    LL p=solve(cur+1,n,M);
    LL ans=pmod(a[cur],p,m);
    return ans;
}

int main()
{
    char s[10];
    LL m,n;
    int cas=0;
    while(scanf("%s",s)==1)
    {
        int l=strlen(s);
        if(s[0]=='#'&&l==1)break;
        m=0;
        for(int i=0;i