取石子游戏

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

 

M.K喜欢收集彩色石子,经过多年的努力,他收集了N(0 < N <= 10000)多石子,因为颜色限制,不同颜色的石子个数不会超过100个,不同的颜色用不同的数进行标号。现在M.K先要玩一个游戏,他要从这N个石子里面取出K个石子(0 < K <= N),先要知道有多少中取法,当然这是一个很简单的问题。不过M.K是一个很爱思考的孩子,考虑从N个石子中取出K个石子的一种取法构成一个集合,他想知道所有取法中集合的总长度是多少,一个集合的长度定义为这个集合中不同元素的个数。

例如有4枚石子,颜色分别为0, 2, 2, 1。从中取出2个有6种,分别是{0, 2},{0, 2}, {0, 1},{1, 2},{1, 2},{2, 2},那么它集合的总长度为2 + 2 + 2 + 2 + 2 + 1 = 11。

 

Input

有多组数据(不超过20),以 0 0 结尾。

对每组数据,第一行为N,K,第二行为数组的N个元素。

 

Output

 结果模1000000007后输出。

Sample Input

4 2
3 1 1 2
0 0

Sample Output

11

Hint

 

Source