Richard has N gold coins. Each coin has a value $A[i]$ associated with it. Richard is too bored after acing his mid-semester examinations. He decides to conduct an experiment that lasts for M days. Each day, Richard can pick any positive number of coins and find the sum of their values. But the value of the chosen coins decreases by K each. Help Richard find the maximum possible cumulative sum at the end of the experiment.

Note : Cumulative sum means the total sum obtained by summing the result he gets each day. Also, the values associated with the coins can become negative during the course of the experiment! The answer can be negative too!

                                             

Input format

The first line consists of 3 integers N, M and K respectively.
N integers follow, where the $i_{th}$ integer ($A[i]$) denotes the initial value associated with the $i_{th}$ coin.

Output format

Print a single integer denoting the answer modulo $10^9 + 7$. Note that answer modulo $10^9 + 7$ is always non-negative even if answer is negative.

Constraints

$1 \leq N \leq 10^5$

$1 \leq K, A[i] \leq 1000$

$1 \leq M \leq 10^9$