問題一覧 > 通常問題

No.1578 A × B × C

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

問題文

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

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

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

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

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

入力

$A\ \ B\ \ C$
$K$

  • $1 \leq A, B, C \leq 10^9$
  • $1 \leq K \leq 10^{12}$
  • 入力はすべて整数である

出力

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

サンプル

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。