#include<bits/stdc++.h>

using namespace std;

int P;
int Reciprocal[46000];
string ExpInfo;


int getReciprocal(int a) {
	int x, n;

	n = P - 2;
	x = 1;
	while (n > 0) {
		if ((n & 1) == 1) {
			x = (x*a) % P;
		}
		a = (a*a) % P;
		n >>= 1;
	}

	return x;
}

int getNumber(unsigned int *pIndex) {
	int num;
	string tmp;
	stringstream ss;

	tmp += ExpInfo[(*pIndex)++];
	while (isdigit(ExpInfo[*pIndex])) {
		tmp += ExpInfo[*pIndex];
		++(*pIndex);
	}
	ss << tmp;
	ss >> num;
	--(*pIndex);

	//cout << num << " ";
	return num;
}

int priorityOfOperation(char c) {

	switch (c) {
	case'(':
		return 3;
	case '*':
	case '/':
		return 2;
	case '+':
	case '-':
		return 1;
	default:
		return 0;
	}
}

bool calculation(stack<int>& digitList, stack<char>& opList) {
	int num2, result;
	char ch;

	ch = opList.top();
	opList.pop();
	num2 = digitList.top();
	digitList.pop();
	result = digitList.top();
	digitList.pop();
	//cout << result << " " << ch << " " << num2 << " = ";

	if (ch == '+' || ch == '-') {
		if (ch == '-') {
			num2 = P - num2;
			//cout << "m=" << num2 << endl;
		}
		result = (result + num2) % P;
	}
	else if (ch == '*' || ch == '/') {
		if (ch == '/') {
			if (num2 == 0) {
				return false;
			}
			num2 = Reciprocal[num2];
		}
		result = (result * num2) % P;
	}
	//cout << result << endl;
	digitList.push(result);
	return true;
}

bool calculationProcess(stack<int>& digitList, stack<char>& opList) {
	int num, nowPriority;
	char cTmp;

	//size = ExpInfo.size();
	for (unsigned int i = 0; i < ExpInfo.size(); ++i) {
		cTmp = ExpInfo[i];

		if (cTmp == ' ') {
			ExpInfo = ExpInfo.erase(i, 1);
			--i;
			continue;
		}
		
		if (isdigit(cTmp)) {
			num = getNumber(&i);
			//cout << num << " ";
			digitList.push(num);
			continue;
		}
		if (opList.empty() || cTmp == '(' || opList.top() == '(') {
			opList.push(cTmp);
			continue;
		}

		nowPriority = priorityOfOperation(cTmp);
		if (nowPriority > priorityOfOperation(opList.top())) {
			opList.push(cTmp);
		}
		else {
			do {
				if (!calculation(digitList, opList)) {
					return false;
				}
			} while (!opList.empty() && opList.top() != '(' && nowPriority <= priorityOfOperation(opList.top()));

			if (cTmp == ')') {
				opList.pop();
			}
			else {
				opList.push(cTmp);
			}
		}
	}

	while (!opList.empty()) {
		if (!calculation(digitList, opList)) {
			return false;
		}
	}

	return true;
}

void solve() {
	stack<int> digitList;
	stack<char> opList;

	if (!calculationProcess(digitList, opList)) {
		cout << "NG" << endl;
		//cout << "numSize:" << digitList.size() << "  opSize:" << opList.size() << endl;
		return;
	}
	cout << ExpInfo << " = ";
	cout << digitList.top() << " (mod " << P << ")" << endl;
	digitList.pop();
	//cout << "numSize:" << digitList.size() << "  opSize:" << opList.size() << endl;
}

int main() {
	char ch;

	while (cin >> P >> ch, P) {
		for (int i = 1; i < P; ++i) {
			Reciprocal[i] = getReciprocal(i);
		}
		getline(cin, ExpInfo);
		solve();
	}

	return 0;
}

