题目背景

歌って踊ろうハッピーバースデイ

砂漠に林檎の木を植えよう

【でんぐり返り】そんじゃバイバイ

あとは谁かが胜手にどうぞ

题目描述

给你两个整数$n$和$k$，再给一个$n$个数的数列，第$i$项是$a_i$，你只需要求

$$\sum^n_{i_1=1}\sum^n_{i_2=i_1+1}...\sum^n_{i_k=i_{k-1}+1} a_{i_1}+a_{i_2}+...+a_{i_k} \pmod {10^9+7} $$

输入格式

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

第二行$n$个整数，第$i$个数字表示$a_i$

输出格式

一个整数表示答案

8 4
2 0 0 8 1 0 3 1

525

10 4
1 3 1 4 5 4 1 8 8 6

3444

12 3
1 2 3 3 2 1 11 12 13 5678 90 12

320540

4 1
1 2 3 4

10

5 2
4 7 8 6 4

116

提示

$n,k,a_i$保证是正整数

数据点编号	$n$的最大值	$a_i$的最大值	其他
#1	$10$	$10^4$	$k\leq 10$
#2	$100$	$10^9$	$k \leq 4$
#3	$1000$		$k=2$
#4	$10^5$		$k=1$
#5			$k=2$
#6			$k=3$
#7			$k=4$
#8			$k=5$
#9			$k\leq 10$
#10	$10^4$		$k\leq 100$