在瓦拉日丁（Varaždin）最好的学校里，有一位优秀的计算机科学老师，她以有趣且不同寻常的想法而闻名。她的名字叫拉娜（Lana），她经常给学生出一些看似不可能或无法解决的问题。每个学生在学年中只需要解决 1 个问题就能以优异的成绩通过课程。到学年结束时还没有解决任何任务的学生将不得不留级。在学期的最后一天，她在黑板上写下了一个极其困难的问题，内容如下：
想象你有一个长度为 $N$ 的数字序列，你可以从开头或结尾（或两者同时）删除一些元素。请问有多少种删除方式，使得删除后的序列中，至少有 1 个数字恰好出现 1 次，至少有 1 个数字恰好出现 2 次，……，并且至少有 1 个数字恰好出现 $K$ 次。
一个名叫弗兰（Fran）的学生，到目前为止还没有解决任何问题，他很快说道：“我知道怎么解决这个问题。”拉娜老师不相信弗兰，并告诉他：“在接下来的 30 分钟内写出代码，我就相信你。如果你做不到，你就得留级。”弗兰不会编程，所以他紧急请求你的帮助来编写代码解决这个任务。在匆忙中，他忘记解释他解决这个任务的想法了。请编写一个代码，输入数字 $N$ 和 $K$ 以及长度为 $N$ 的序列，解决拉娜的问题以帮助弗兰。
输入格式
第一行包含 2 个正整数 $N$ ($1 \le N \le 10^5$) 和 $K$ ($1 \le K \le 4$)。
第二行包含 $N$ 个正整数 $a_i$ ($1 \le a_i \le N$)。
输出格式
第一行输出一个整数，表示满足任务条件的删除方式的数量。如果两种删除方式中，被删除的索引集合不同，则视为不同的删除方式。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 20 | $N \le 1000$ |
| 2 | 15 | $1 \le a_i \le K$ 对于所有 $i = 1, 2, \dots, N$ |
| 3 | 35 | $K = 1$ |
| 4 | 50 | 无附加限制 |
样例
输入格式 1
3 1 1 2 1
输出格式 1
6
说明
删除后的可能序列为：$[1], [2], [1], [1, 2], [2, 1], [1, 2, 1]$，在所有这 6 个序列中，都有一个数字恰好出现 1 次。
输入格式 2
6 3 6 5 6 4 5 5
输出格式 2
1
说明
删除后满足“至少有 1 个数字恰好出现 1 次，至少有 1 个数字恰好出现 2 次，且至少有 1 个数字恰好出现 3 次”的唯一序列是给定的原序列。
输入格式 3
6 2 5 4 5 2 6 5
输出格式 3
5
样例说明
样例说明 1
删除后的可能序列为：$[1], [2], [1], [1, 2], [2, 1], [1, 2, 1]$，在所有这 6 个序列中，都有一个数字恰好出现 1 次。
样例说明 2
删除后满足“至少有 1 个数字恰好出现 1 次，至少有 1 个数字恰好出现 2 次，且至少有 1 个数字恰好出现 3 次”的唯一序列是给定的原序列。