No.1448 Sum and Difference
タグ : / 解いたユーザー数 96
作問者 :
shiomusubi496
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)$
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もしくは右上の雲マークをクリックしてアカウントを作成してください。