# K Increasing Subsequence 2

hard

For the given sequence A with n elements find the number of strictly increasing subsequences with k elements. Note: This question is same as K Increasing Subsequence, but this time array can have numbers from 1 to 10^9 and can have duplicates.

## Constraints

1. 1 <= n <= 10^5 2. 1 <= k <= 11 3. 1 <= A[i] <= 10^9 5. A can contain duplicates 6. Output may not fit in 32 bit signed integer

## Format

### Input

First line contains two integer n and k following n lines contains elements of sequence A[1] A[2] ....A[n]

### Output

Print one number the andwer to question

## Example

Sample Input

5 2
1
1
3
8
2

### Sample Output

7