#include<bits/stdc++.h>
using namespace std;
#define int long long
int MOD;
int mod_pow(int x,int n,int mod){
  int res=1LL;
  while(n>0){
    if(n&1) (res*=x)%=mod;
    (x*=x)%=mod;
    n>>=1;
  }
  return res;
}
int mod_inverse(int x,int mod){
  return mod_pow(x,mod-2,mod);
}
int flag;
int expression(string s,int&p);
int term(string s,int&p);
int factor(string s,int&p);
int number(string s,int&p);

int expression(string s,int&p){
  int res=term(s,p);
  while(p<(int)s.size()){
    if(s[p]=='+'){
      p++;
      (res+=term(s,p))%=MOD;
      continue;
    }
    if(s[p]=='-'){
      p++;
      (res+=MOD-term(s,p))%=MOD;
      continue;
    }
    if(flag) return 0;
    break;
  }
  return res;
}

int term(string s,int&p){
  int res=factor(s,p);
  while(p<(int)s.size()){
    if(s[p]=='*'){
      p++;
      (res*=factor(s,p))%=MOD;
      continue;
    }
    if(s[p]=='/'){
      p++;
      int tmp=factor(s,p);
      if(tmp==0){
	flag=1;
	break;
      }
      (res*=mod_inverse(tmp,MOD))%=MOD;
      continue;
    }
    if(flag) return 0;
    break;
  }
  return res;
}

int factor(string s,int&p){
  int res;
  if(s[p]=='('){
    p++;
    res=expression(s,p);
    p++;
  }else{
    res=number(s,p);
  }
  return res;
}

int number(string s,int&p){
  int res=0;
  while(p<(int)s.size()&&isdigit(s[p]))
    res=res*10+s[p++]-'0';
  return res;
}

signed main(){
  string s;
  while(getline(cin,s),s[0]!='0'){
    int latte=s.find(':');
    string x=s.substr(0,latte);
    //cout<<latte<<": "<<x<<endl;
    MOD=stoll(x);
    s.erase(s.begin(),s.begin()+latte+1);
    string t;
    for(int i=0;i<(int)s.size();i++) if(s[i]!=' ') t+=s[i];
    int p=0;
    flag=0;
    int ans=expression(t,p);
    if(flag) cout<<"NG"<<endl;
    else cout<<t<<" = "<<ans<<" (mod "<<MOD<<")"<<endl;
  }
  return 0;
}