#include <cstdio>
#include <iostream>
#include <string>
#include <cctype>
using namespace std;
typedef string::const_iterator State;
int p;
bool flag;
int number(char* &begin);
int term(char* &begin);
int factor(char* &begin);
int expression(char* &begin);

int mod_pow(int x,int n){
	int res=1;
	while(n>0){
		if(n&1)res=res*x%p;
		x=x*x%p;
		n>>=1;
	}
	return res;
}

int number(char* &begin){
	int ret=0;
	while(isdigit(*begin)){
		ret*=10;
		ret+=*begin-'0';
		begin++;
	}
	ret%=p;
	return ret;
}

int term(char* &begin){
	int ret=factor(begin);
	while(1){
		if(*begin=='*'){
			begin++;
			ret=ret*factor(begin)%p;
		}else if(*begin=='/'){
			begin++;
			int da=factor(begin);
			if(da==0)flag=false;
			int k=mod_pow(da,p-2);
			ret=ret*k%p;
		}else break;
	}
	return ret;
}

int factor(char* &begin){
	if(*begin=='('){
		begin++;
		int ret=expression(begin);
		begin++;
		return ret;
	}else return number(begin);
}

int expression(char* &begin){
	int ret=term(begin);
	while(1){
		if(*begin=='+'){
			begin++;
			ret=(ret+term(begin))%p;
		}else if(*begin=='-'){
			begin++;
			ret=(ret+p-term(begin))%p;
		}else break;
	}
	return ret;
}

char str[2][100001];

int main(void){
	while(1){
		scanf("%d:",&p);
		if(p==0)break;
		flag=true;
		int len=0;
		fgets(str[0],100000,stdin);
		for(int i=0;i<100000;i++){
			if(str[0][i]!=' ' && str[0][i]!='\n'){
				str[1][len]=str[0][i];
				len++;
			}
		}
		char* v=str[1];
		int res=expression(v);
		if(!flag)printf("NG\n");
		else printf("%s = %d (mod %d)\n",str[1],res,p);
	}
	return 0;
}