Giải bài trực tuyến

Cho 1 dãy số gồm N(0 < N ≤ 10000) số tự nhiên S1,S2,...,Sn (0 ≤ S[i] ≤ 100000), Hãy đếm số lượng dãy con tăng có độ dài K(0 < k ≤ 50).

Input

Dòng đầu tiên là hai số tự nhiên N và K.

N dòng tiếp sau mô tả dãy S.

Output

Số lượng dãy con thỏa mãn theo Module 5000000.

Example

Input:
4 3
1
2
2
10

Output:
2

Giải Thích : Có 2 dãy con thỏa mãn (S1,S2,S4) và (S1,S3,S4) : (1,2,10).