問題一覧 > 通常問題

No.1448 和差算

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 66
作問者 : cpcznksutbeoacpcznksutbeoa / テスター : shiomusubi496shiomusubi496 turtle0123turtle0123
3 ProblemId : 5050 / 出題時の順位表
問題文最終更新日: 2021-04-03 09:33:07

問題文

整数 $A,B,C,D,N$ が与えられます。
この時、次の条件を全て満たす整数列の組 $(a,b)$ を考えます。

条件:

  • $A \le a_0 \le B$
  • $C \le b_0 \le D$
  • $1 \le i \le N$ となる任意の整数 $i$ について
    $a_i=a_{i-1}-b_{i-1}$
    $b_i=a_{i-1}+b_{i-1}$

この時の $a_N+b_N$ の値として考えられるものはいくつかありますが、そのうち最大のものを $10^9+7$ で割った余りを出力してください。
なお、 $a_N+b_N$ を $10^9+7$ で割った余りの最大値ではなく、 $a_N+b_N$ の最大値を $10^9+7$ で割った余りを求めることに注意してください。

制約

  • 入力は全て整数
  • $-10^9 \le A,B,C,D \le 10^9$
  • $A \le B$
  • $C \le D$
  • $0 \le N \le 10^{18}$

入力

$A~B~C~D$
$N$

出力

答えを $10^9+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)$
ですので、 $a_1+b_1$ の最大値は $6$ です。

サンプル2
入力
-5 -4 -3 -2
2
出力
1000000005

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

サンプル3
入力
3141 5926 5358 9793
238462643383279502
出力
845706131

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

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