Učiteljica (선생님)

Varaždin의 최고 학교에는 컴퓨터 과학 교사 Lana가 있었다. 그녀는 학생들에게 풀 수 없거나 풀기 어려운 문제를 자주 냈다. 학생은 한 학년 동안 문제를 한 개만 풀면 우수한 성적으로 통과할 수 있었다. 학년이 끝날 때까지 한 문제도 풀지 못한 학생은 유급해야 했다.

학기 마지막 날, 그녀는 다음 문제를 칠판에 적었다. 길이가 $N$인 수열이 있다. 앞, 뒤, 또는 양쪽 끝에서 원소를 몇 개든 지울 수 있다. 삭제 후 남은 수열에서 1부터 $K$까지 모든 $i$에 대해, 정확히 $i$번 나타나는 수가 적어도 하나 있어야 한다. 이런 삭제 방법은 모두 몇 가지인가?

아직 문제를 하나도 풀지 못한 Fran은 풀이 방법을 안다고 말했다. 그러나 그는 코딩을 할 줄 몰라서 이 문제를 푸는 프로그램을 작성해 달라고 부탁했다.

첫 줄에 양의 정수 $N$ (1 ≤ $N$ ≤ 10^5)과 $K$ (1 ≤ $K$ ≤ 4)가 주어진다.

둘째 줄에는 수열의 원소인 양의 정수 $N$개 $a_i$ (1 ≤ $a_i$ ≤ $N$)가 주어진다.

조건을 만족하는 서로 다른 삭제 방법의 수를 한 줄에 출력한다. 두 삭제 방법 중 한쪽에서는 삭제된 인덱스가 다른 쪽에서는 삭제되지 않았다면, 두 방법은 다른 방법이다.