Trong trường học tốt nhất ở Cần Thơ, có một giáo viên tin học xuất sắc nổi tiếng với những ý tưởng thú vị và khác thường. Tên cô ấy là Ngân, và cô thường đưa cho học sinh những bài toán bất khả thi hoặc không thể giải. Mỗi học sinh chỉ cần giải \(1\) bài toán trong năm học để vượt qua lớp với điểm xuất sắc. Những học sinh không giải được bài toán nào đến cuối năm sẽ phải ở lại lớp. Vào ngày cuối cùng của trường, cô ấy viết một bài toán cực kỳ khó lên bảng, như sau:

Hãy tưởng tượng bạn có một dãy số có độ dài \(N\), và bạn có thể xóa một số phần tử từ đầu hoặc cuối (hoặc cả hai). Có bao nhiêu cách bạn có thể thực hiện việc xóa sao cho sau khi xóa, phải 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à ít nhất \(1\) số xuất hiện đúng \(K\) lần.

Một học sinh tên Hạo, người chưa giải được bài toán nào cho đến nay, nhanh chóng nói: "Tôi biết cách giải bài toán này." Giáo viên Ngân không tin Hạo và nói với anh: "Viết code trong 30 phút tiếp theo, và tôi sẽ tin cậu. Nếu không, cậu sẽ phải ở lại lớp." Hạo không biết lập trình, vì vậy anh ấy khẩn cấp nhờ bạn giúp viết code để giải bài toán này. Trong lúc vội vàng, anh ấy quên giải thích ý tưởng giải bài toán. Hãy viết code nhận input là các số \(N\) và \(K\), dãy \(N\) phần tử, và giải quyết câu hỏi của Ngân để giúp Hạo.

Dữ liệu vào

• Trong dòng đầu tiên, có \(2\) số nguyên dương \(N\) \((1 \le N \le 10^5)\) và \(K\) \((1 \le K \le 4)\) từ mô tả bài toán.
• Trong dòng thứ hai, có \(N\) số nguyên dương \(a_i\) \((1 \le a_i \le N)\), các số từ mô tả bài toán.

Dữ liệu ra

Trong dòng đầu tiên, in một số nguyên, số lượng cách xóa khác nhau sao cho các điều kiện từ bài toán được thỏa mãn. Hai cách xóa là khác nhau nếu có một chỉ số không bị xóa trong cách này, nhưng bị xóa trong cách kia.

Chấm điểm

Input 1

3 1
1 2 1

Output 1

6

Input 2

6 3
6 5 6 4 5 5

Output 2

1

Input 3

6 2
5 4 5 2 6 5

Output 3

5

Làm rõ ví dụ đầu tiên: Các dãy có thể sau khi xóa là: [1], [2], [1], [1, 2], [2, 1], [1, 2, 1], và trong mỗi dãy trong số 6 dãy, có một số xuất hiện đúng một lần.

Làm rõ ví dụ thứ hai: Dãy duy nhất sau khi xóa trong đó 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à ít nhất 1 số xuất hiện đúng ba lần là dãy N số đã cho.