题目描述

给定长度为 $n$ 的序列 $a_{1\sim n}$，定义其和谐度为 $\sum_{i=1}^n\sum_{j=i+1}^na_i\cdot a_j$。

你可以进行至多 $k$ 次操作，每次选定一个 $1\leq i\leq n$，令 $a_i\gets a_i+1$。

最大化最终序列的和谐度。由于答案可能很大，输出其对 $10^9+7$ 取模后的值。

输入格式

第一行两个整数 $n,k$。

第二行 $n$ 个整数 $a_{1\sim n}$。

输出格式

一行一个整数表示答案。

2 2
4 1

12

样例解释 1

样例解释：两次操作都用在第二个元素上，和谐度为 4*3=12。

3 3
7 1 3

61

样例解释 2

样例解释：三次操作都用在第二个元素上，和谐度为 74+73+4*3=61。

数据范围

对于 $30\%$ 的数据，$n\leq 3000$，$k=1$。

对于 $60\%$ 的数据，$n\leq 5\times 10^5$，$k\leq 100$。

对于 $100\%$ 的数据，$2\leq n\leq 5\times 10^5$，$0\leq k\leq 10^9$，$0\leq a_i\leq 10^9$。