問題一覧 > 通常問題

No.1448 和差算

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 92
作問者 : Falcon_Falcon_ / テスター : shiomusubi496shiomusubi496 ytqm3ytqm3
3 ProblemId : 5050 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-03-04 14:03:58

問題文

整数 A,B,C,D と正整数 N が与えられます。

この時、次の条件を全て満たす整数列の組 (a,b) を考えます。

条件

  • Aa0B
  • Cb0D
  • 1iN となる任意の整数 i について
    • ai=ai1bi1
    • bi=ai1+bi1

この時の aN+bN の値として考えられるものはいくつかありますが、そのうち最大のものを 109+7 で割った余りを出力してください。

なお、 aN+bN109+7 で割った余りの最大値ではなく、 aN+bN の最大値を 109+7 で割った余りを求めることに注意してください。

制約

  • 入力は全て整数
  • 109AB109
  • 109CD109
  • 0N1018

入力

A B C D
N

出力

答えを 109+7 で割った余りを出力してください。
最後に改行してください。

サンプル

サンプル1


入力

2 3 4 5
1

出力

6

(a,b) として考えられるのは

  • a=(2,2),b=(4,6)
  • a=(3,1),b=(4,7)
  • a=(2,3),b=(5,7)
  • a=(3,2),b=(5,8)
ですので、 a1+b1 の最大値は 6 です。

サンプル2


入力

-5 -4 -3 -2
2

出力

1000000005

入力や答えがマイナスになる場合に注意してください。

サンプル3


入力

3141 5926 5358 9793
238462643383279502

出力

845706131

109+7 で割ったあまりを求めることに注意してください。

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