#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);
  }
}

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;
    if(res==-1)cout<<"NG"<<endl;
    else{
      cout<<s<<" = ";
      cout<<res<<" (mod "<<P<<")"<<endl;
    }
  }
  
  return 0;
}

Measured memory_bytes: 1392