#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long LL;
int inv[46000];
char ch[256];
int term(int p);
int primary_expression(int p);

int pow_2(int a,int n,int p) {
	int x=1;
	while(n>0) {
		if(n&1) x=(x*a)%p;
		a=(a*a)%p;
		n>>=1;
	}
	return x;
}
enum TokenType {
	INT=1,ADD,SUB,MUL,DIV,LP,RP,END
};
struct Token{
	TokenType type;
	int value;
};
vector<Token> V;
bool get_token(void) {
	char ch;
	while((ch=getchar())==' ') {}
	Token tkn;
	if(ch=='\n'||ch=='\0') {
		tkn.type=END;
	}else if(ch=='+') {
		tkn.type=ADD;
	}else if(ch=='-') {
		tkn.type=SUB;
	}else if(ch=='*') {
		tkn.type=MUL;
	}else if(ch=='/') {
		tkn.type=DIV;
	}else if(ch=='(') {
		tkn.type=LP;
	}else if(ch==')') {
		tkn.type=RP;
	}else {
		tkn.type=INT;
		int value=0;
		do {
			value*=10;
			value+=(ch-'0');
		}while(isdigit(ch=getchar()));
		ungetc(ch,stdin);
		tkn.value=value;
	}
	V.push_back(tkn);
	return(tkn.type!=END);
}
int pos=0;
int expression(int p) {
	int val1=term(p),val2;
	while(V[pos].type==ADD||V[pos].type==SUB) {
		TokenType type=V[pos].type;
		pos++;
		val2=term(p);
		if(val1==-1||val2==-1) return -1;
		if(type==ADD) {
			val1=(val1+val2)%p;
		}else {
			val1=(val1-val2+p)%p;
		}
	}
	return val1;
}
int term(int p) {
	int val1=primary_expression(p),val2;
	while(V[pos].type==MUL||V[pos].type==DIV) {
		TokenType type=V[pos].type;
		pos++;
		val2=primary_expression(p);
		if(val1==-1||val2==-1) return -1;
		if(type==MUL) {
			val1=(val1*val2)%p;
		}else {
			if(val2==0) return -1;
			val1=(val1*inv[val2])%p;
		}
	}
	return val1;
}
int primary_expression(int p) {
	int value;
	if(V[pos].type==INT) {
		value=V[pos].value;
	}else if(V[pos].type==LP) {
		pos++;
		value=expression(p);
	}
	pos++;
	return value;
}
int main() {
	int p;
	ch[ADD]='+';
	ch[SUB]='-';
	ch[MUL]='*';
	ch[DIV]='/';
	ch[LP]='(';
	ch[RP]=')';
	while(scanf("%d:",&p),p) {
		for(int i=1;i<p;i++) inv[i]=pow_2(i,p-2,p);
		V.clear();
		while(get_token()) {}
		pos=0;
		int val=expression(p);
		if(val==-1) {printf("NG\n"); continue;}
		for(int i=0;i+1<V.size();i++) {
			if(V[i].type==INT) {
				printf("%d",V[i].value);
			}else {
				putchar(ch[V[i].type]);
			}
		}
		printf(" = %d (mod %d)\n",val,p);
	}
}