問題一覧 > 通常問題

No.1275 綺麗な式

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 62
作問者 : 神鳥奈紗神鳥奈紗 / テスター : 57tggx57tggx
5 ProblemId : 5245 / 出題時の順位表
問題文最終更新日: 2020-10-30 22:23:30

問題文

神鳥さんは壁に次のような問題が書かれているのを発見しました。

$\displaystyle \left( a+\sqrt{b} \right)^n + \left( a-\sqrt{b} \right)^n$を求めてください。

しかし、神鳥さんはこの問題を解くことができません。あなたは神鳥さんの代わりにこの問題を解いてください。

ただし、この値は非常に大きくなることがあるので、$10^9+7$で割ったあまりを出力してください。

また、この値は整数になることが保証されています。

入力

$a\ b$
$n$

  • 入力は全て整数である。
  • $0 \le a , b \le 10^9$
  • $0 \le n \le 10^{18}$
  • $a^2=b$ かつ $n=0$となるようなケースは存在しない。
  • $a+b+n\neq0$
  • 出力

    最後に改行してください。

    サンプル

    サンプル1
    入力
    2 4
    2
    出力
    16

    サンプル2
    入力
    1 16
    5
    出力
    2882

    サンプル3
    入力
    111 111
    111
    出力
    370378144

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