Get Stable Periods Count (Fungible :)

A non-empty contiguous period of the income array is stable if it contains at most k distinct income values. Count all stable periods modulo 1000000007; periods with different start or end positions are counted separately.

输入格式

The first line contains n k; the second line contains the incomes. 1≤n≤100000, 1≤k≤n, −10^9≤income≤10^9.

输出格式

Output a single integer, the answer.

样例 1

输入：

3 1
1 2 1

输出：

3

样例 2

输入：

4 2
2 -3 2 -3

输出：

10

样例 3

输入：

3 1
5 5 5

输出：

6

样例说明

The answers are 3, 10 and 6. A contiguous range of equal incomes may also span multiple dates.