有限体電卓

0以外のすべての実数の逆数は実数になりますが、整数の逆数が整数になるとは限りません。Ｃ言語などで 3.0/2.0*2.0 = 3.0 なのに 3/2*2 = 2 になってしまうのはこのためです。ですが、素数で割った余りが等しい整数を同じものとみなすと、0以外のすべての整数が逆数をもつようにできます。

æ•´æ•° x と y ã‚’ p で割った余りが等しいとき、x ≡ y (mod p) と書きます。p が素数のとき、このような x と y を同じものとみなすなら、すべての整数 n は0から p−1 までのどれかの整数 x に対して x ≡ n (mod p) となるので、けっきょく { 0, 1, 2, ..., p−1 } という集合だけからなる世界を考えればよいことがわかります。

この世界での加減乗除は以下のようになります。

• 加算 x+y の値は、x+y ≡ z (mod p) となる 0 から p−1 までの数 z になります。
• 減算 x−yの値は、y+m ≡ 0 (mod p) となる 0 から p−1 までの数 m（これが y に相当します）について、x−y ≡ x + m (mod p) となることから得られます。たとえば、p = 5のとき、4+1 ≡ 0 (mod 5) となります。このとき、2−4 ≡ 2+1 ≡ 3 (mod 5) より、2−4の値は3になります。
• ä¹—ç®— x*y の値は、x*y ≡ z (mod p) となる 0 から p−1 までの数 z になります。
• 除算 x/y の値は、y*d ≡ 1 (mod p)となる 0 から p−1 までの数 d （これがyの逆数になります）について、x/y ≡ x*d (mod p) となることから得られます。たとえば、p = 5 のとき、2*3 ≡ 1 (mod 5) より 3 は 2 の逆数になります。このとき、1/2 ≡ 1*3 ≡ 3 (mod 5) より、1/2 の値は 3 になります。

このようにして加減乗除の四則演算がすべて0からp−1の範囲に収まります。このとき、集合 { 0,1,...,p−1 } ã‚’ p の有限体といいます。この有限体の中で、加減乗除、0 から p−1 までの数、カッコを使って 算術式を構成することができます。

p の有限体の 0 以外のすべての要素が逆数をもつことは、フェルマーの小定理と呼ばれる有名な定理 a^p−1 ≡ 1 (mod p) からわかります（ただし、p は素数、a と p は互いに素）。p の有限体のすべての要素 x は p と互いに素なので、この定理から x*x^p-2 ≡ 1 (mod p) となり x^p-2 が x の逆数になるからです。

では、素数と式が与えられたときに、その素数の有限体で式を計算する電卓プログラムを作成してください。

入力

入力は複数のデータセットからなる。入力の終わりは0の後にコロンが１つ続くだけの行 0: で示される。各データセットは以下の形式で与えられる。

p:exp

データセットは１行であり、p (2 ≤ p ≤ 46000) は素数、exp は算術式を示す。exp は加減乗除（それぞれ +, -, *, /）とカッコ、0 から p−1 までの数から構成される。演算子、数、カッコなどの前後には1つ以上の空白が現れる可能性がある。exp の長さは 100,000 を超えない。

データセットの数は 1000 を超えない。

出力

データセットごとに、計算結果を出力する。出力形式は以下の通りである。

exp = val (mod p)

val は、p の有限体での算術式 exp の計算結果である。ただし、0 での除算が含まれるときは NG と出力する。また、exp に現れる加減乗除、カッコ、数の前後には空白を空けないこと。ただし、= の前後には空白を一つずつ空ける。また、valと開きカッコの間、modとp の間にも空白を一つずつ空ける。

入力例

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:

出力例

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)