Problem1091--编程课奖励

1091: 编程课奖励

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 39  Solved: 21
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI老师的Java编程课有N名同学参加了期末考试,现在他们在PIPI老师办公室门外排成一排,领取奖励。  
PIPI老师决定奖励他们每人若干颗爪哇咖啡豆。具体规则如下:
每人奖励至少一颗,最多K颗咖啡豆。  
对于前后相邻的2名同学,如果他们期末分数一样,那么他们得到的咖啡豆数量也要一样;否则分数高的同学得到较多的咖啡豆。  
现在按他们排队的顺序给定每名同学的期末考试分数,请你计算PIPI老师有多少种不同的奖励方法满足以上规则。由于方案数可能非常多,你只需要输出模1000000007的结果即可。

Input

多组数据
第一行包含两个N和K。  
第二行包含N个整数A1, A2, ... AN。  
1 <= N <= 100000  
1 <= K <= 100  
0 <= Ai <= 100

Output

输出一个整数,代表一共有多少不同方案,对1000000007取模

Sample Input

3 3  
88 100 90

Sample Output

5

Source/Category