ストーリー


RSA 暗号は、世界で広く使われている公開鍵暗号アルゴリズムです。

高橋くんは自分でも RSA 暗号を使ってみようと思いました。

そのためには鍵を作ることが必要です。

RSA 暗号の鍵生成は以下のような手順で行います。

鍵生成


RSA 暗号では、鍵を生成するために適当な素数 と、自然数 を選びます。

自然数 を、

と置きます。

ここで、 とすると、 未満の自然数で、 と互いに素である必要があります。( はオイラーのφ関数 )

自然数 を、

と置きます。

は多くの場合合成数であるため、 の計算は(拡張)ユークリッドの互除法により行います。

このようにして計算された値を使い、公開鍵と秘密鍵を作成することができます。

  • 公開鍵:
  • 秘密鍵:

問題文


相異なる素数 と正整数 が与えられます。

秘密鍵 を生成し、 を出力してください。

ただし、 とし、 となるような最小の非負整数とします。

制約


  • は素数であり、 である
  • は互いに素である
  • 入力はすべて整数である

入力


出力


  • 行目に を出力せよ。
  • 行目に を出力せよ。

入出力例


入力例1
5 11 3
出力例1
55
27

のとき、 となります。

入力例2
97 997 64295
出力例2
96709
10007
入力例3
998244353 998244853 5
出力例3
996492287418565109
199298457084415181

出力は ビット整数で表される範囲を超える可能性があります。

Submit


Go (1.14)