K Increasing Subsequence 1

medium
Question Solve Solutions 
For the given sequence A with n different elements find the number of increasing subsequences with k  elements.

Input Format

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

Output Format

Print one number the andwer to question

Constraints

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

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input
5
3
1
2
3
5
4
Output
7
Previous
Multiples Of 3
Next
K Increasing Subsequence 2

Related Questions

medium Max In An Interval - Range Query medium Sum Of Interval medium Max In A Interval - Range Query Point Update medium What's At Idx - Point Query Range Update medium Sum Of Range - Range Query Range Update medium Maximum Sum hard Sum Of Squares hard 2d Segment Tree medium Toggle Bulbs medium Prime Divide medium Multiples Of 3 hard K Increasing Subsequence 2 hard Domino Principle hard Xor On Segment hard Interesting Array hard Complex Queries