Description

dXqwq 有一个长度为 n 的排列 a 和一个长度为 m 的队列 q，初始时 q 中的元素全部为 0，她会对于 x=1∼n 依次执行以下操作：

• 如果队首元素 q1<ax，则弹出队首，并将 ax 放入队尾。

在操作结束后，dXqwq 定义自己的潜力值为 q 中所有元素的和。

dXqwq 想知道，对于给定排列 b 通过重排得到的所有排列 a，自己会得到的潜力值的和。因为答案实在太大了，她只需要你输出答案对 109+7 取模的值。

Input Format

从文件 potential.in 中读入数据。

第一行输入两个整数 n,m。

第二行输入 n 个整数 bi

Output Format

输出到文件 potential.out 中。

输出一行一个整数，代表潜力值的和对 109+7 取模的值。

3 2
1 2 3

28

Hint

样例

Input 1

	3 2
1 2 3
	

		
	

Output 1

	28
	

		
	

Input 2

	10 4
1 2 3 4 5 6 7 8 9 10
	

		
	

Output 2

	105878520
	

		
	

Input 3

	见下发的 potential3.in。
该样例满足测试点 4 的性质。
	

		
	

Output 3

	见下发的 potential3.ans。
该样例满足测试点 4 的性质。
	

		
	

数据范围

本题共 20 个测试点，全部测试点满足 2≤m≤n≤500，1≤bi<109+7，bi 严格递增。

测试点	n≤	m≤
1	5	5
2	10	10
3∼4	18	2
5∼7	50	2
8∼10	50	3
11∼12	50	4
13∼15	50	50
16∼18	200	200
19∼20	500	500

样例解释

对于第一组样例，a 有以下六种可能：

• a=[1,2,3]，q=[2,3]，潜力值为 5。
• a=[1,3,2]，q=[3,2]，潜力值为 5。
• a=[2,1,3]，q=[1,3]，潜力值为 4。
• a=[2,3,1]，q=[2,3]，潜力值为 5。
• a=[3,1,2]，q=[3,1]，潜力值为 4。
• a=[3,2,1]，q=[3,2]，潜力值为 5。

它们的潜力值之和为 5+5+4+5+4+5=28。

对于第二组样例，如果 a=[1,9,2,6,3,5,7,8,10,4]，操作过程如下：

• 初始时 q=[0,0,0,0]。
• 弹出 0，插入 1，q=[0,0,0,1]。
• 弹出 0，插入 9，q=[0,0,1,9]。
• 弹出 0，插入 2，q=[0,1,9,2]。
• 弹出 0，插入 6，q=[1,9,2,6]。
• 弹出 1，插入 3，q=[9,2,6,3]。
• 5,7,8 都没有 9 大，所以不进行修改。
• 弹出 9，插入 10，q=[2,6,3,10]。
• 弹出 2，插入 4，q=[6,3,10,4]。

所以 q=[6,3,10,4]，潜力值为 23。

Source

CSP-S 2024模拟题