← 返回题目列表

Codeforces · 597/C

C. 子序列

中文机器翻译题面 查看原题

对于给定的具有 n 个不同元素的序列,找到具有 k + 1 个元素的递增子序列的数量。保证答案不大于8·1018。

输入

第一行包含两个整数值 n 和 k (1 ≤ n ≤ 105, 0 ≤ k ≤ 10) — 序列的长度和递增子序列中的元素数量。

接下来的 n 行每行包含一个整数 ai (1 ≤ ai ≤ n) — 序列的元素。所有值 ai 都不同。

输出

打印一个整数——问题的答案。

示例

输入 #1

5 2
1
2
3
5
4

输出 #1

7