#include<cstdio>
#include<iostream>
#include<string>
#include<stack>
#include<vector>
#include<queue>
#include<utility>

using namespace std;

int mod;

string valid="0123456789+-*/() ";

string getP(string str)
{
	int res=0;
	int id=-1;
	for(int i=0;i<str.size();i++)
	{
		if(str[i]==':')
		{
			id=i;
			break;
		}
		res*=10;
		res+=(str[i]-'0');
	}
	mod=res;
	string str2=str.substr(id+1);
	return str2;
}

long long ex(int a,int e)
{
	if(e==0) return 1;
	long long tmp=ex(a,e/2);
	tmp*=tmp;
	tmp%=mod;
	if(e%2==1) tmp*=a;
	tmp%=mod;
	return tmp;
}

int getNum(string str)
{
	int res=0;
	for(int i=0;i<str.size();i++)
	{
		res*=10;
		res+=str[i]-'0';
	}
	return res;
}

bool isdigit(char ch)
{
	return '0'<=ch&&ch<='9';
}

bool isvalid(char ch)
{
	for(int i=0;i<valid.size();i++) if(valid[i]==ch) return true;
	return false;
}

vector<string> parse(string str)
{
	str+=' ';
	vector<string> res;
	string num;
	bool in=false;
	for(int i=0;i<str.size();i++)
	{
		if(!isvalid(str[i])) break;
		//cout<<"x"<<str[i]<<"\n";
		if(str[i]==' ')
		{
			if(in)
			{
				in=false;
				res.push_back(num);
				num.clear();
			}
			continue;
		}
		else if(isdigit(str[i]))
		{
			in=true;
			num+=str[i];
		}
		else
		{
			if(in)
			{
				in=false;
				res.push_back(num);
				num.clear();
			}
			string tmp;
			tmp+=str[i];
			res.push_back(tmp);
		}
	}
	if(in) res.push_back(num);
	return res;
}

stack<char> tmp;
queue<string> rpn;

int pri(char ch)
{
	if(ch=='+') return 0;
	if(ch=='-') return 0;
	if(ch=='*') return 1;
	if(ch=='/') return 1;
	return 2;
}

void getRPN(vector<string> vec)
{
	while(!tmp.empty()) tmp.pop();
	for(int i=0;i<vec.size();i++)
	{
		if(isdigit(vec[i][0]))
		{
//			cout<<"push"<<vec[i]<<"\n";
			rpn.push(vec[i]);
		}
		else if(vec[i][0]=='(') tmp.push(vec[i][0]);
		else if(vec[i][0]==')')
		{
			while(!tmp.empty()&&tmp.top()!='(')
			{
				string str;
				str+=tmp.top();
				rpn.push(str);
//				if(str[0]=='(') printf("z\n");
//				cout<<"push"<<str<<"\n";
				tmp.pop();
			}
			tmp.pop();
		}
		else
		{
			while(!tmp.empty()&&pri(tmp.top())>=pri(vec[i][0])&&tmp.top()!='(')
			{
				string str;
				str+=tmp.top();
				rpn.push(str);
				tmp.pop();
//				cout<<"push"<<str<<"\n";
			}
			tmp.push(vec[i][0]);
		}
	}
	while(!tmp.empty())
	{
		string str;
		str+=tmp.top();
		rpn.push(str);
		tmp.pop();
//		cout<<"push"<<str<<"\n";
	}
}

stack<int> st;
bool ok;

int solveRPN()
{
	while(!st.empty()) st.pop();
	ok=true;
	while(!rpn.empty())
	{
		string str=rpn.front();
		rpn.pop();
		if(isdigit(str[0]))
		{
			int num=0;
			for(int i=0;i<str.size();i++)
			{
				num*=10;
				num+=str[i]-'0';
			}
			st.push(num);
		}
		else
		{
		//	if(st.empty()) for(;;);
			int a=st.top();
			st.pop();
		//	if(st.empty()) for(;;);
			int b=st.top();
			st.pop();
			//b op a
			if(str[0]=='+')
			{
				int n=a+b;
				n%=mod;
				st.push(n);
			}
			else if(str[0]=='-')
			{
				int n=b-a;
				n%=mod;
				if(n<0) n+=mod;
				st.push(n);
			}
			else if(str[0]=='*')
			{
				int n=a*b;
				n%=mod;
				st.push(n);
			}
			else if(str[0]=='/')
			{
				if(a%mod==0) ok=false;
				int r=ex(a,mod-2);
				b*=r;
				b%=mod;
				if(b<0) b+=mod;
				st.push(b);
			}
			else for(;;);
		}
	}
	return st.top();
}

void output(int res,vector<string> vec)
{
	if(ok==false)
	{
		cout<<"NG"<<"\n";
		return;
	}
	for(int i=0;i<vec.size();i++) cout<<vec[i];
	cout<<" = "<<res<<" (mod "<<mod<<")\n";
	return;
}

bool check(vector<string> vec)
{
	int in=0;
	for(int i=0;i<vec.size();i++)
	{
		if(vec[i][0]=='(') in++;
		else if(vec[i][0]==')') in--;
		if(in<0) return false;
		if(i>1)
		{
			if(isdigit(vec[i][0])&&isdigit(vec[i-1][0])) return false;
			if((!isdigit(vec[i][0]))&&(!isdigit(vec[i-1][0])))
			{
				if(vec[i][0]!='('&&vec[i-1][0]!=')')
				{
					return false;
				}
			}
		}
	}
	if(in>0) return false;
	return true;
}

int solve(string str)
{
	str=getP(str);
	while(!tmp.empty()) tmp.pop();
	while(!rpn.empty()) rpn.pop();
	vector<string> vec=parse(str);
	if(check(vec)==false) for(;;);
//	for(int i=0;i<vec.size();i++) cout<<"ab"<<vec[i]<<"cd"<<"\n";
//	printf("aaa\n");
	getRPN(vec);
	int res=solveRPN();
	//if(ok) printf("----------%d-----%d\n",mod,res);
	//else   printf("-----------------NG\n");
	output(res,vec);
	return 0;
}

char ch[100100];

int main()
{
	while(true)
	{
		gets(ch);
		if(ch[0]=='0') break;
		string str;
		for(int i=0;ch[i]!='\0';i++) str+=ch[i];
		solve(str);
	}
	return 0;
}

Measured memory_bytes: 4696