Bob is preparing for the Robbing Balloons contest, he wants to practice like no one ever practiced.
In order to efficiently practice, he wants to solve some problems and needs to calculate how much time he needs to solve these problems. Bob needs $x$ minutes to solve a single problem, but after solving $k$ problems he will take a break for $y$ minutes.
For example if $x=2,y=4,k=3$
To solve 6 problems:
To solve 7 problems:
Let $F(n)$ be the number of minutes he needs to solve $n$ problems, Bob is wondering about the value of $F(n)$ for each $n$ in the range $[l,r]$, he wants to know the summation of all these values, in other words find $\sum _{l \le n \le r} {F(n)}$. Since the answer can be very big, print it module $10^9 + 7$.
The input contains 5 integers $l,r,x,y,k$($1 \le l \le r \le 10^9$)($1 \le x,y,k \le 10^9$).
Print a single integer, the required summation module $10^9 + 7$.
| Input | Output |
|---|---|
6 7 2 4 3 Copy
|
38 Copy
|
1 1000000000 2 5 7 Copy
|
142857223 Copy
|
Notice that Bob has to take a first break if there's at least $k + 1$ problems, a second break if there's at least $2k + 1$ problems, a third when there's at least $3k + 1$ problems and so on, so if bob has $n$ problems he will take $\lfloor \frac {n-1}{k} \rfloor$ breaks. With that we can see that $F(n) = nx + \lfloor \frac {n-1}{k} \rfloor y$.
Let's assume for now that $l=1$, the summation $\sum _{1 \le n \le r} {F(n)}$ can be broken down to two parts, first part is:
$$\sum _{1 \le n \le r} n*x = x \sum _{1 \le n \le r} n = x \frac {n (n + 1)}{2}$$
The second part is:
$$\sum _{1 \le n \le r} \lfloor \frac {n-1}{k} \rfloor y = y (\sum _{1 \le n \le zk} \lfloor \frac {n-1}{k} \rfloor + \sum _{zk + 1 \le n \le r} \lfloor \frac {n-1}{k} \rfloor ) $$
Where $zk$ is the largest multiple of $k$ less than $r$.
Notice that the first $k$ values of the left summation($\sum _{1 \le n \le zk} \lfloor \frac {n-1}{k} \rfloor$) are $0,0,...,0$, the second $k$ values are $1,1,...,1$, the third $k$ values are all $2$s and so on, so the left summation is equal to $\sum _{1 \le i \le z} (i-1)k = k \frac{(z-1)z}{2}$.
The right summation is equal to $z(r-zk)$, so overall:
$$ \sum _{1 \le n \le r} {F(n)} = x \frac {n (n + 1)}{2} + y ( k \frac{(z-1)z}{2} + z(r-zk) ) $$
We solved the problem when $l=1$, to get the full answer, let $S(n) = \sum _{1 \le n \le r} {F(n)}$, then our final answer should be $S(r) - S(l-1)$.