Cho dãy gồm \(n\) số nguyên \(a_1,a_2,…,a_n (1≤a_i≤n)\). Ta có thể xóa đi một số phần tử ở đầu hoặc ở cuối hoặc ở cả hai đầu của dãy số.

Cho biết có bao nhiêu cách thực hiện xóa sao cho sau khi xóa, dãy thu được có ít nhất 1 số xuất hiện đúng một lần, ít nhất 1 số xuất hiện đúng hai lần, …, và có ít nhất 1 số xuất hiện đúng \(k\) lần.

Dữ liệu vào:

• Dòng đầu tiên gồm hai số nguyên dương \(n,k (n≤10^5;k≤4).\)

• Dòng thứ hai gồm n số nguyên dương \(a_1,a_2,…,a_n (1≤a_i≤n)\)

  Hai số ghi trên cùng một dòng được phân cách nhau bởi một dấu cách.

Kết quả:

• Ghi một số nguyên là số lượng dãy số sau khi thực hiện xóa thỏa mãn yêu cầu của đầu bài. Hai cách xóa gọi là khác nhau nếu tồn tại một vị trí mà không được xóa ở lần này, nhưng được xóa ở lần khác.

Ràng buộc:

• Subtask 1: (20% số điểm): n≤1000

• Subtask 2: (15% số điểm): 1≤a_i≤k.

• Subtask 3: (25% số điểm): k=1.

• Subtask 4 :(40% số điểm): Không có ràng buộc gì thêm.

Sample Input

3 1
1 2 1

Sample Output

6

Sample Input

6 3
6 5 6 4 5 5

Sample Output

1

Sample Input

6 2
5 4 5 2 6 5

Sample Output

5

Giải thích test 1: \

• 6 dãy số thỏa mãn là: [1]; [2]; [1]; [1,2]; [2,1]; [1,2,1].