#include <bits/stdc++.h>
using namespace std;

struct Mint
{
	int value;
	int mod;
	
	Mint ( int mod ) : value(0), mod(mod) {}
	Mint ( int value, int mod ) : value((value + mod) % mod), mod(mod) {}
	
	Mint operator  + (  int x ) const { return ( Mint (value + (x % mod), mod) ); }
	Mint operator  - (  int x ) const { return ( Mint (value - (x % mod), mod) ); }
	Mint operator  * (  int x ) const { return ( Mint (value * (x % mod), mod) ); }
	Mint operator += (  int x )       { return ( *this = *this + x ); }
	Mint operator -= (  int x )       { return ( *this = *this - x ); }
	Mint operator *= (  int x )       { return ( *this = *this * x ); }
	Mint operator  + ( Mint x ) const { return ( *this + x.value ); }
	Mint operator  - ( Mint x ) const { return ( *this - x.value ); }
	Mint operator  * ( Mint x ) const { return ( *this * x.value ); }
	Mint operator += ( Mint x )       { return ( *this = *this + x ); }
	Mint operator -= ( Mint x )       { return ( *this = *this - x ); }
	Mint operator *= ( Mint x )       { return ( *this = *this * x ); }

	Mint operator  ^ (  int n ) const 
	{
		Mint g = Mint(value, mod), ans = Mint(1, mod);
		while ( n > 0 ) {
			if ( (n & 1) == 1 ) {
				ans *= g;
			}
			g *= g;
			n >>= 1;
		}
		return ( ans );
	}

	Mint operator  ~ ()         const { return ( (*this) ^ (mod - 2) ); }
	Mint operator  / (  int x ) const { return ( (*this) * (~Mint(x, mod)) ); }
	Mint operator /= (  int x )       { return ( *this = *this / x ); };
	Mint operator  / ( Mint x ) const { return ( *this / x.value ); }
	Mint operator /= ( Mint x )       { return ( *this = *this / x ); };

	bool operator == (  int x ) const { return ( value == x ); }
	bool operator == ( Mint x ) const { return ( value == x.value ); }
	

};

Mint valueRead(int &cur, string &S, int mod);
char operationCheck(int &cur, string &S);
Mint getItem(int &cur, string &S, int mod);
Mint calculation(int cur, string& S, int mod);

bool error;

int main()
{
	string S;

	while ( getline(cin, S), S != "0:" ) {
		int p;
		int cur = 0;
		error = false;
		{
			string temp;
			while ( S[cur] != ':' ) {
				temp += S[cur];
				cur++;
			}
			p = atoi(temp.c_str());
		}

		cur++;

		Mint ans = calculation(cur, S, p);
		if ( error ) {
			cout << "NG" << endl;
		} else {
			string T;
			for ( int i = cur; i < S.size(); i++ ) {
				if ( S[i] != ' ' ) {
					T += S[i];
				}
			}
			cout << T << " = " << ans.value << " (mod " << p << ")" << endl;
		}
			
	}
	return ( 0 );
}

Mint calculation(int cur, string& S, int mod)
{	
	//cout << "calc" << " " << cur << " " << S[cur] << endl;
	Mint val = getItem (cur, S, mod);
	char op;
	//和差
	while ( (op = operationCheck(cur, S)) != '#' ) {
		//積商を求める
		Mint next_val = getItem(cur, S, mod);
		//足し引き
		switch ( op ) {
		case '+' :
			val += next_val;
			break;
		case '-' :
			val -= next_val;
			break;
		}
	}
	return ( val );
}

Mint getItem(int &cur, string &S, int mod)
{
	while ( cur < S.size() && S[cur] != ')' && (S[cur] == '+' || S[cur] == '-' || S[cur] == ' ') ) cur++;

	if ( cur < S.size() && S[cur] != ')' ) {
		//cout << "getItem" << endl;
		char op;
		Mint val = valueRead(cur, S, mod);
		while ( (op = operationCheck(cur, S)) != '#' && op != '+' && op != '-' ) {
			Mint next_val = valueRead (cur, S, mod);
			//かけわり
			switch ( op ) {
			case '*' :
				val *= next_val;
				break;
			case '/' :
				if ( next_val == Mint(0, mod) ) {
					error = true;
				} else {
					val /= next_val;
				}
				break;
			}
		}
		return ( val );
	} else {
		return ( Mint(0, mod) );
	}
}

Mint valueRead(int &cur, string &S, int mod)
{
	while ( S[cur] == '*' || S[cur] == '/' || S[cur] == ' ' ) cur++;
	//cout << "valueRead A" << " ";
	if ( S[cur] == '(' ) {
		//cout << "(" << endl;
		Mint data = calculation (cur + 1, S, mod);
		int cnt = 1;
		cur++;
		while ( cnt > 0 ) {
			if ( S[cur] == '(' ) cnt++;
			if ( S[cur] == ')' ) cnt--;
			cur++;
		}
		//cout << ")" << endl;
		//cout << data.value << endl;
		return ( data );
	} else {
		string reader;
		while ( isdigit(S[cur]) ) {
			reader += S[cur];
			cur++;
		}
		//cout << reader << endl;
		return ( Mint (atoi(reader.c_str()), mod) );
	}
}

char operationCheck(int &cur, string &S)
{
	while ( cur < S.size() && S[cur] != ')' && S[cur] == ' ' ) cur++;

	if ( cur < S.size() && S[cur] != ')' ) {
		return ( S[cur] );
	} else {
		return ( '#' );
	}
}



Measured memory_bytes: 3280