#include <iostream>
#include <cstdio>
#include <algorithm>
#include <sstream>
#include <vector>
#include <cstring>
#include <map>
#include <cassert>
using namespace std;

int dp[31][1<<16];

long long P;

long long bpow(long long A,long long B){
	return B ? bpow(A*A%P,B/2) * (B&1?A:1)%P : 1;
}
long long inv(long long n){
	if(n==0)throw "NG";
	return bpow(n,P-2);
}
long long A();
long long B();
long long C();

string s;
int p;

long long A(){
	long long l = B();
	while(s[p] == '+' || s[p] == '-' ){
		if( s[p] == '+' ){
			p++;
			l += B();
			l %= P;
		}else{
			p++;
			l -= B();
			l %= P;
			l += P;
			l %= P;
		}
	}
	return l;
}
long long B(){
	long long l = C();
	while(s[p] == '*' || s[p] == '/' ){
		if( s[p] == '*' ){
			p++;
			l *= C();
			l %= P;
		}else{
			p++;
			l *= inv(C());
			l %= P;
		}
	}
	return l;
}
long long C(){
	if( s[p] == '(' ){
		p++;
		long long res = A();
		p++;
		return res;
	}
	if( s[p] == '-' ){
		p++;
		return -C();
	}
	long long ans = 0;
	while(s[p] >= '0' && s[p] <= '9' ){
		ans = ans * 10 + s[p] - '0';
		ans %= P;
		p++;
	}
	return ans;
}
int main(){
	while( getline(cin,s) && s[0] != '0' ){
		int pos = s.find(":");
		string a = s.substr(0,pos);
		string b = s.substr(pos+1);
		b.erase(remove(b.begin(),b.end(),' '),b.end());
		b.erase(remove(b.begin(),b.end(),'\r'),b.end());
		
		s = b + "~";
		P = atoi(a.c_str());
		p = 0;
		try{
			long long r = A();
			cout << b << " = " << r << " (mod " << P << ")" << endl;
		}catch(const char *a){
			cout << "NG" << endl;
		}
			
	}
}