#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <stack>
#include <climits>
#include <deque>
#include <bitset>
#include <cassert>
#include <ctime>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int dy[]={-1,0,1,0},dx[]={0,1,0,-1};
// adjust problem by problem
const double EPS=1e-8;
const double PI=acos(-1.0);
#ifdef __GNUC__
int popcount(int n){return __builtin_popcount(n);}
int popcount(ll n){return __builtin_popcountll(n);}
#endif
#ifndef __GNUC__
template<class T> int popcount(T n){int cnt=0;while(n){if(n%2)cnt++;n/=2;}return cnt;}
#endif
template<class T>int SIZE(T a){return a.size();}
template<class T>string IntToString(T num){string res;stringstream ss;ss<<num;return ss.str();}
template<class T>T StringToInt(string str){T res=0;for(int i=0;i<SIZE(str);i++)res=(res*10+str[i]-'0');return res;}
template<class T>T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template<class T>T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T> void PrintSeq(T &a,int sz){for(int i=0;i<sz;i++){cout<<a[i];if(sz==i+1)cout<<endl;else cout<<' ';}}
bool EQ(double a,double b){return abs(a-b)<EPS;}
void fastStream(){cin.tie(0);std::ios_base::sync_with_stdio(0);}
vector<string> split(string str,char del){
  vector<string> res;
  for(int i=0,s=0;i<SIZE(str);i++){
    if(str[i]==del){if(i-s!=0)res.push_back(str.substr(s,i-s));s=i+1;}
    else if(i==SIZE(str)-1){res.push_back(str.substr(s));}
  }
  return res;
}

// int P;
// // O(logn)で繰り返し二乗法によりnum^p%modを計算
// ll mod_pow(ll num,ll p,ll mod){
//   ll mul=num;
//   ll res=1;
//   while(p){
//     if(p%2)res=(res*mul)%mod;
//     p/=2;
//     mul=(mul*mul)%mod;
//   }
//   return res;
// }
// // fermerの小定理を用いてmodの割算を計算
// ll div_mod(ll num,ll mod){
//   return mod_pow(num,mod-2,mod);
// }


char s[1000001];

// pii equation(int p);
// pii factor(int p);
// pii term(int p);

// pii equation(int p) {
//   pii r = factor(p);
//   if(r.first==-1)return pii(-1,-1);
//   while (s[r.second] == '+'||s[r.second] == '-') {
//     bool isPlus=(s[r.second] == '+');
//     pii r_ = factor(r.second+1);
//     if(r_.first==-1)return pii(-1,-1);
//     if(isPlus){
//       r.first = (r.first + r_.first);
//       while(r.first>=P)r.first-=P;
//       r.second      = r_.second;
//     }
//     else{
//       r.first = (P + r.first - r_.first);
//       while(r.first>=P)r.first-=P;
//       r.second      = r_.second;
//     }
//   }
//   return r;
// }
// pii factor(int p) {
//   pii r = term( p);
//   if(r.first==-1)return pii(-1,-1);
//   while (s[r.second] == '*'||s[r.second]=='/') {
//     bool isMul=(s[r.second] == '*');
//     pii r_ = term( r.second+1);
//     if(r_.first==-1)return pii(-1,-1);
//     if(isMul){
//       r.first = (r.first * r_.first)%P;
//       r.second      = r_.second;
//     }
//     else{
//       if(r_.first==0)return pii(-1,-1);
//       r.first = (r.first * div_mod(r_.first,P))%P;
//       r.second      = r_.second;
//     }
//   }
//   return r;
// }

// pii term( int p) {
//   if (s[p] == '(') {
//     pii r = equation( p+1);
//     if(r.first==-1)return pii(-1,-1);
//     r.second++; // skip ')'
//     return r;
//   } else {
//     int value = 0;
//     while (isdigit(s[p]))
//       value = value * 10 + (s[p++] - '0');
//     return pii(value, p);
//   }
// }

int P;
// O(logn)で繰り返し二乗法によりnum^p%modを計算
ll mod_pow(ll num,ll p,ll mod){
  ll mul=num;
  ll res=1;
  while(p){
    if(p%2)res=(res*mul)%mod;
    p/=2;
    mul=(mul*mul)%mod;
  }
  return res;
}
// fermerの小定理を用いてmodの割算を計算
ll div_mod(ll num,ll mod){
  return mod_pow(num,mod-2,mod);
}
 
int analysis(int head,int tail){
  bool isNumber=true;
  for(int i=head;i<=tail;i++){
    if(!(s[i]>='0'&&s[i]<='9')){
      isNumber=false;
      break;
    }
  }
  if(isNumber){
    int num=0;
    for(int i=head;i<=tail;i++)num=num*10+(s[i]-'0');
    return num;
  }
  else{
    if(s[head]=='('){
      int cnt=1;
      bool ok=true;
      for(int i=head+1;i<tail;i++){
        if(s[i]=='(')cnt++;
        else if(s[i]==')')cnt--;
        if(cnt==0){
          ok=false;
          break;
        }
      }
      if(ok&&cnt==1&&s[tail]==')')
        return analysis(head+1,tail-1);
    }
    {
      int cnt=0;
      for(int i=tail;i>=head;i--){
        if(s[i]==')')cnt++;
        else if(s[i]=='(')cnt--;
        else if(cnt==0&&(s[i]=='+'||s[i]=='-')){
          int res1=analysis(head,i-1);
          int res2=analysis(i+1,tail);
          if(res1==-1||res2==-1)return -1;
          if(s[i]=='+')return (res1+res2)%P;
          else return (res1-res2+P)%P;
        }
      }
    }
    {
      int cnt=0;
      for(int i=tail;i>=head;i--){
        if(s[i]==')')cnt++;
        else if(s[i]=='(')cnt--;
        else if(cnt==0&&(s[i]=='*'||s[i]=='/')){
          int res1=analysis(head,i-1);
          int res2=analysis(i+1,tail);
          if(res1==-1||res2==-1)return -1;
          if(s[i]=='*')return (res1*res2)%P;
          else{
            if(res2==0)return -1;
            return (res1*div_mod(res2,P))%P;
          }
        }
      }
    }
  }
  return -1;
}
 


char instr[1000001];
int main(){
  fastStream();
  //ifstream cin("in.txt");
  string str;
  while(scanf("%d:",&P)&&P){
    fgets(instr,1000001,stdin);
    int len=strlen(instr);
    int sz=0;
    for(int i=0;i<len-1;i++)
      if(instr[i]!=' ')s[sz++]=instr[i];
    s[sz++]='\0';
    //int res=equation(0).first;
    int res=analysis(0,sz-2);
    if(res==-1)cout<<"NG"<<endl;
    else{
      cout<<s<<" = ";
      cout<<res<<" (mod "<<P<<")"<<endl;
    }
  }
  
  return 0;
}

Measured memory_bytes: 1416