#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>

using namespace std;

int prime;

//??°??????????????????
int func(int x,int n){
	if(n == 0)
		return 1;
	int res = func(x*x%prime,n/2);
	if(n % 2 == 1)res = res*x%prime;
	return res;
}

int main(){

	int tmp,op1,work,count,work2,index,p,ans;
	char* buf = new char[150000];
	char* line = new char[150000]; //??????????????¨??????
	char calc;
	stack<int> NUM,work_num;
	stack<char> OP,work_op;

	bool numFLG,zero_divFLG;

	while(true){
		fgets(buf,150000,stdin);
		if(buf[0] == '0')break;

		//???????????????buf????¶?????????¢??§line?????¢?¨?????????????

		//??????????´???°?????????
		prime = 0;
		for(index = 0; buf[index] != ':';index++){
			prime = 10*prime + buf[index] - '0';
		}

		//??????????????????????????¢?¨???????
		p = 0;
		for(index+=1;buf[index] != '\n' && buf[index] != '\0';index++){
			if(buf[index] == ' '){
				//Do nothing
			}else{
				line[p++] = buf[index];
			}
		}
		line[p] = '\0'; //???????????????????´?

		tmp = 0;
		numFLG = false;
		zero_divFLG = false;	//0????????????????¨??????????????????°
		//????????????????§???????????????°?????????0???p-1?????§?????°???????????´??????????????????negFLG??????

		//???0?????§break????????????????????¨
		while(!NUM.empty())NUM.pop();
		while(!work_num.empty())work_num.pop();
		while(!OP.empty())OP.pop();
		while(!work_op.empty())work_op.pop();

		for(int k = 0; line[k] != '\0'; k++){
			if(line[k] >= '0' && line[k] <= '9'){ //??°????????´???
				numFLG = true;
				tmp = 10*tmp + (line[k] - '0');

				//???????????????)??????????????¨??????????????§??¨???!!!!:???????¢??????????
				if(line[k+1] == '\0'){ //?????????????¬????NULL???????????°????????????????????¨?????????????????????!!!!!!????????????

					if(OP.empty() == false && (OP.top() == '*' || OP.top() == '/')){ //???????????????????????????????????????????????????????????????????¨???????????????????
						calc = OP.top();
						OP.pop();
						op1 = NUM.top();
						NUM.pop();

						if(calc == '*'){
							NUM.push((tmp*op1)%prime);
						}else{
							if(tmp == 0){
								zero_divFLG = true;
								break;
							}else{ //???????????????

								int d = func(tmp,prime-2);
								op1 *= d;
								op1 %= prime;
							}
							NUM.push(op1);
						}
					}else{
						NUM.push(tmp);
					}

					work = NUM.top(); //???????????°????????°???????????????????????°??????????????????1??????
					NUM.pop();
					work_num.push(work);

					while(!NUM.empty()){
						calc = OP.top();
						OP.pop();

						work_op.push(calc);

						work = NUM.top();
						NUM.pop();
						work_num.push(work);
					}

					//??????????????????????????§?????????????????????
					work = work_num.top();
					work_num.pop();

					while(!work_num.empty()){
						calc = work_op.top();
						work_op.pop();

						if(calc == '+'){
							work += work_num.top();
							work %= prime;
						}else if(calc == '-'){
							work -= work_num.top();
							while(work < 0){
								work += prime;
							}
						}else if(calc == '*'){
							work *= work_num.top();
							work %= prime;
						}else{
							//work /= work_num.top();
							if(work_num.top() == 0){
								zero_divFLG = true;
								break;
							}else{
								int d = func(work_num.top(),prime-2);
								work *= d;
								work %= prime;
							}
						}
						work_num.pop();
					}
					ans = work;
				}
				if(zero_divFLG)break;
			}else{ //??°?????§????????´???

				if(numFLG == true){

					if(OP.empty() == false && (OP.top() == '*' || OP.top() == '/')){ //???????????????????????????????????????????????????????????????????¨???????????????????
						calc = OP.top();
						OP.pop();
						op1 = NUM.top();
						NUM.pop();

						if(calc == '*'){
							NUM.push((tmp*op1)%prime);
						}else{
							if(tmp == 0){
								zero_divFLG = true;
								break;
							}else{ //???????????????
								int d = func(tmp,prime-2);
								op1 *= d;
								op1 %= prime;

							}
							NUM.push(op1);
						}
					}else{
						NUM.push(tmp);
					}

					numFLG = false;
					tmp = 0;
				}

				if(line[k] == '+' ||line[k] == '*' || line[k] == '/' || line[k] == '('){
					OP.push(line[k]);
				}else if(line[k] == '-'){	//??????????????°????????´??????????????????-??????????????¨????????±??£?????????
					OP.push('-');
				}else if(line[k] == ')'){ //??????????????§??????????????´?????????????????§??¨???!!!!

					//????????£???:??????????????????????????????????????????????????¬??§?????§????????????????????¨??°???????????????????????????
					work = NUM.top(); //???????????°????????°???????????????????????°??????????????????1??????
					NUM.pop();
					work_num.push(work);

					count = 0;

					while(true){
						calc = OP.top();
						OP.pop();
						if(calc == '(')break;	//????????¬??§?????°????????????????????????

						count++;

						work_op.push(calc);

						work = NUM.top();
						NUM.pop();
						work_num.push(work);
					}

					if(count == 0){ // 123*(-1)+122= ?????????????????????
						work = work_num.top();
						work_num.pop();
					}else{

						//??????????????????????????§?????????????????????
						work = work_num.top();
						work_num.pop();

						while(!work_num.empty()){
							calc = work_op.top();
							work_op.pop();

							if(calc == '+'){
								work += work_num.top();
								work %= prime;
							}else if(calc == '-'){
								work -= work_num.top();
								while(work < 0){
									work += prime;
								}
							}else if(calc == '*'){
								work *= work_num.top();
								work %= prime;
							}else{
								//work /= work_num.top();
								if(work_num.top() == 0){
									zero_divFLG = true;
									break;
								}else{
									int d = func(work_num.top(),prime-2);
									work *= d;
									work %= prime;
								}
							}
							work_num.pop();
						}
					}

					//????????????<4-3*(1+1)+3=>
					if(OP.empty() == false && OP.top() == '*'){
						OP.pop();
						work2 = NUM.top();
						NUM.pop();
						work *= work2;
						work %= prime;
					}else if(OP.empty() == false &&OP.top() == '/'){
						OP.pop();
						work2 = NUM.top();
						NUM.pop();

						if(work == 0){
							zero_divFLG = true;
							break;
						}else{
							int d = func(work,prime-2);
							work2 *= d;
							work = work2;
							work %= prime;
						}
					}

					NUM.push(work); //?????????????????¬??¶????????????????????????

					if(line[k+1] == '\0'){
						work = NUM.top(); //???????????°????????°???????????????????????°??????????????????1??????
						NUM.pop();
						work_num.push(work);

						while(!NUM.empty()){
							calc = OP.top();
							OP.pop();

							work_op.push(calc);

							work = NUM.top();
							NUM.pop();
							work_num.push(work);
						}

						//??????????????????????????§?????????????????????
						work = work_num.top();
						work_num.pop();

						while(!work_num.empty()){
							calc = work_op.top();
							work_op.pop();

							if(calc == '+'){
								work += work_num.top();
								work %= prime;
							}else if(calc == '-'){
								work -= work_num.top();
								while(work < 0){
									work += prime;
								}
							}else if(calc == '*'){
								work *= work_num.top();
								work %= prime;
							}else{
								//work /= work_num.top();
								if(work_num.top() == 0){
									zero_divFLG = true;
									break;
								}else{
									int d = func(work_num.top(),prime-2);
									work *= d;
									work %= prime;
								}
							}
							work_num.pop();
						}
						ans = work;

					}


				}else{	//???????????´???
					//Do nothing
				}
			}
			if(zero_divFLG)break;
		}
		if(zero_divFLG)printf("NG\n");
		else{
			printf("%s = %d (mod %d)\n",line,ans,prime);
		}
	}
	return 0;
}

Measured memory_bytes: 2808