Dãy con khác nhau 2

Cho mảng \(A\) gồm \(n\) phần tử. Hai dãy con (không nhất thiết liên tiếp) của \(A\) được coi là khác nhau nếu dãy giá trị của chúng khác nhau (xét theo thứ tự các phần tử).

Yêu cầu: Đếm số lượng dãy con khác nhau khác rỗng có độ dài đúng \(k\) của \(A\).

Input

• Dòng đầu tiên gồm hai số nguyên \(n, k\) (\(1 \le k \le n \le 2000\)).

• Dòng thứ hai gồm \(n\) số nguyên \(A_1, A_2, \ldots, A_n\) (\(1 \le A_i \le 2000\)).

Output

In ra một số nguyên duy nhất là số lượng dãy con khác nhau độ dài \(k\) của \(A\), lấy phần dư khi chia cho \(123456789\).

Example

Input:

3 2
1 2 2

Output:

2

Note

Với \(A = [1, 2, 2]\), các dãy con độ dài \(2\) (xét theo vị trí) là \((A_1, A_2) = (1, 2)\), \((A_1, A_3) = (1, 2)\) và \((A_2, A_3) = (2, 2)\). Trong đó \((A_1, A_2)\) và \((A_1, A_3)\) có cùng dãy giá trị \((1, 2)\) nên chỉ được tính một lần. Vậy có \(2\) dãy con khác nhau: \((1, 2)\) và \((2, 2)\).