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 \cdot 1018.

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

Next n lines contains one integer ai (1 \le ai \le n) each - elements of sequence. All values ai are different.

Print one integer - the answer to the problem.