問題一覧 > 通常問題

No.1578 A × B × C

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 233
作問者 : magsta / テスター : 👑 Kazun
8 ProblemId : 6405 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-01 17:17:44

問題文

3 つの正の整数 A,B,C と正の整数 K が与えられます。まず、黒板に A,B,C の 3 つの数字が書かれてあります。

以下の操作を K 回行います。

  • 黒板に書かれた数字 3 つそれぞれを、同時に 他の 2 つの数を掛け合わせた数で書き直す。

操作が終わった後の黒板に書かれた 3 つの数の積を 109+7 で割った余りを求めてください。

ヒント : フェルマーの小定理 (wikipediaに飛びます)

入力

A  B  C
K

  • 1≤A,B,C≤109
  • 1≤K≤1012
  • 入力はすべて整数である

出力

求めた値を出力し、最後に改行せよ。

サンプル

サンプル1
入力
2 3 1
1
出力
36

黒板に書かれた数は 3, 2, 6 となり、これの積である 36 が求めるものとなります。

サンプル2
入力
1 1 1
4879314
出力
1

何回操作しても 1, 1, 1 のままです。

サンプル3
入力
390421437 291872136 531083427
292874319324
出力
664210506

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。