跳至正文
题库1845
#1845

Subsequences

查看题目操作

Subsequences

题目描述

For the given sequence with n different elements find the number of increasing subsequences with k+1 elements. It is guaranteed that the answer is not greater than 8·1018.

Input

First line contain two integer values n and k (1≤n≤105,0≤k≤10) − the length of sequence and the number of elements in increasing subsequences.

Next n lines contains one integer ai (1≤ai≤n) each − elements of sequence. All values ai are different.

Output

Print one integer − the answer to the problem.

Examples

5 2
1
2
3
5
4
7