問題一覧 > 通常問題

No.1448 Sum and Difference

レベル : / AI推定難易度 : 1350 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 96
作問者 : Falcon_ / テスター : shiomusubi496 ytqm3
お気に入りにしたユーザー ProblemId : 5050 / 自分の提出
問題文最終更新日: 2026-10-17 09:26:45
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
新入生プログラミングコンテスト 2021(昼の部) (順位表) の他の問題:

Problem Statement

You are given integers $A,B,C,D$ and an integer $N$ that is at least $0$.

Consider pairs of integer sequences $(a,b)$ that satisfy all of the following conditions.

Conditions

  • $A \le a_0 \le B$
  • $C \le b_0 \le D$
  • For every integer $i$ such that $1 \le i \le N$:
    • $a_i=a_{i-1}-b_{i-1}$
    • $b_i=a_{i-1}+b_{i-1}$

There are several possible values of $a_N+b_N$. Output the largest of them modulo $10^9+7$.

Note that you are asked for the maximum value of $a_N+b_N$, taken modulo $10^9+7$, and not for the maximum of $a_N+b_N$ modulo $10^9+7$.

Constraints

  • All inputs are integers.
  • $-10^9 \le A \le B \le 10^9$
  • $-10^9 \le C \le D \le 10^9$
  • $0 \le N \le 10^{18}$

Input

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

Output

Output the answer modulo $10^9+7$.
Print a newline at the end.

Sample

Sample 1


Input

2 3 4 5
1

Output

6

The possible $(a,b)$ are

  • $a=(2,-2),b=(4,6)$
  • $a=(3,-1),b=(4,7)$
  • $a=(2,-3),b=(5,7)$
  • $a=(3,-2),b=(5,8)$
so the maximum value of $a_1+b_1$ is $6$.

Sample 2


Input

-5 -4 -3 -2
2

Output

1000000005

Be careful with cases where the input or the answer is negative.

Sample 3


Input

3141 5926 5358 9793
238462643383279502

Output

845706131

Remember to compute the remainder modulo $10^9+7$.

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