Finite Field Calculator

The reciprocals of all non-zero real numbers are real numbers, but the reciprocals of integers are not necessarily integers, which is why in C and other languages, 3.0/2.0*2.0 = 3.0 but 3/2*2 = 2. However, if we consider integers with equal remainders divided by a prime number to be the same, we can make sure that all integers except 0 have reciprocals.

When the integers x and y are divided by p and the remainders are equal, we write x ≡ y (mod p). if p is prime and we consider such x and y to be the same, then every integer n is x ≡ n (mod p) for any integer x from 0 to p−1. This means that we only need to consider a world consisting of the set { 0, 1, 2, ..., p−1 }.

The addition, subtraction, multiplication, and division in this world are as follows:

• The value of addition x+y will be a number z from 0 to p−1 such that x+y ≡ z (mod p).
• The value of the subtraction x−y is obtained from the fact that x−y ≡ x + m (mod p) for any number m between 0 and p−1 (which corresponds to y) where y+m ≡ 0 (mod p). For example, when p = 5, we have 4+1 ≡ 0 (mod 5). In this case, from 2−4 ≡ 2+1 ≡ 3 (mod 5), the value of 2−4 is 3.
• The value of the multiplication x*y will be a number z from 0 to p−1 such that x*y ≡ z (mod p).
• The value of the division x/y is obtained from the fact that x/y ≡ x*d (mod p) for any number d between 0 and p−1 (which is the reciprocal of y), where y*d ≡ 1 (mod p). For example, when p = 5, 2*3 ≡ 1 (mod 5), so 3 is the reciprocal of 2. In this case, 1/2 ≡ 1*3 ≡ 3 (mod 5), and the value of 1/2 is 3.

In this way, all the four arithmetic operations of addition, subtraction, multiplication, and division fall within the range of 0 to p−1. At this point, the set { 0,1,.... ,p−1 } is called the finite field of p. Within this finite field, we can construct arithmetic expressions using addition, subtraction, multiplication, division, numbers between 0 and p−1, and parentheses.

The fact that all non-zero elements of a finite field of p have reciprocals can be seen from a famous theorem called Fermat's Little Theorem a^p−1 ≡ 1 (mod p) (where p is prime and a and p are prime to each other), because all elements x of a finite field of p are prime to p, so by this theorem we get x*x^p-2 ≡ 1 (mod p) and x^p-2 is the reciprocal of x.

Given a prime number and an expression, create a calculator program that calculates the expression in the finite of that prime number.

Input

The input consists of multiple data sets. The end of the input is indicated by the line 0:, which is just a zero followed by a colon. Each data set is given in the following format.

p:exp

The dataset is a single line, where p (2 ≤ p ≤ 46000) denotes a prime number, exp denotes an arithmetic expression, and exp consists of addition, subtraction, multiplication, division (+, -, *, /, respectively), parentheses, and a number from 0 to p−1. One or more spaces may appear before and after the operators, numbers, parentheses, etc. The length of exp does not exceed 100,000.

The number of datasets should not exceed 1000.

Output

Output the calculation results for each data set. The output format is as follows.

exp = val (mod p)

val is the result of computing the arithmetic expression exp in a finite body of p. However, when division by zero is included, the output is NG. Do not leave spaces before or after addition, multiplication, division, parentheses, or numbers that appear in exp. However, leave one space before and after =. Also, leave one space between val and the opening parenthesis, and between mod and p.

Sample Input

5: 2 - 3
17: 1 + 3 * (2 + 3 / 5 * 2) + 7
11: 1 / 8 - 5 - 8 * 2
19: 8 / (2 - 3 * 7)
1153: 10 * 3 / 7 + ( 50 + 81 / 22 ) + 11
0:

Sample Output

2-3 = 4 (mod 5)
1+3*(2+3/5*2)+7 = 4 (mod 17)
1/8-5-8*2 = 8 (mod 11)
NG
10*3/7+(50+81/22)+11 = 915 (mod 1153)

---