問題文

整数 $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 \le B \le 10^9$
• $-10^9 \le C \le D \le 10^9$
• $0 \le N \le 10^{18}$

入力

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

出力

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

サンプル

2 3 4 5
1

6

-5 -4 -3 -2
2

1000000005

3141 5926 5358 9793
238462643383279502

845706131