#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef string::const_iterator state;

int mod_pow(int n,int m,int mod){
    if(!m)return 1;
    int x=mod_pow(n,m/2,mod);
    x=x*x%mod;
    if(m&1)x=x*n%mod;
    return x;
}

int p;
bool flag;
int number(state &b){
    int ret=0;
    while(isdigit(*b)){
        ret=ret*10+(*b-'0');
        b++;
    }
    return ret;

}
int expression(state&);

int factor(state &b){
    if(*b=='('){
        b++;
        int ret=expression(b);
        b++;
        return ret;
    }
    else return number(b);
}

int term(state &b){
    int ret=factor(b);
    while(true){
        if(*b=='*'){
            b++;
            ret=(ret*factor(b))%p;
        }
        else if(*b=='/'){
            b++;
            int a=factor(b);
            if(a==0){
                flag=false;
                return 0;
            }
            ret=ret*mod_pow(a,p-2,p)%p;
        }
        else break;
    }
    return ret;
}


int expression(state &b){
    int ret=term(b);
    while(flag){

        if(*b=='+'){
            b++;
            ret=(ret+term(b))%p;
        }
        else if(*b=='-'){
            b++;
            ret=(ret-term(b)+p)%p;
        }
        else break;
    }
    return ret;
}

signed main(){
    string str;
    char ig;
    while(cin>>p>>ig,getline(cin,str),p){
        flag=true;
        string s;
        for(int i=0;i<str.size();i++)if(str[i]!=' ')s+=str[i];
        s+=" ";

        state start=s.begin();
        int v=expression(start);
        if(flag)cout<<s<<"= "<<v<<" (mod "<<p<<")"<<endl;
        else cout<<"NG"<<endl;
    }

    return 0;
}