Subsequences
说明
C. Subsequences
time limit per test
1 secondmemory limit per test
256 megabytesinput
standard inputoutput
standard outputFor 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
Input
5 2
1
2
3
5
4
Output
7
样例
