It can be solved using dynamic programming. First use coordinate compression to get the values from 1...N Let dp[i][j] be number of subsequences of length j ending with i. Then, dp[i][j]=dp[i-1][j-1]+dp[i-2][j-1]+.....+dp[1][j-1];

This will take O(N*N*K) time.

Since a dp[i][j] is a cumulative sum of 0....i-1 we can use BIT for this purpose. We will have to make to make K BITs so that a particular state can be answered in O(logn) time. Complexity(O(N*K*logN))

There is a copy of this problem: 597C - Подпоследовательности, my solution using BIT: 15007060, Deemo's one: 14269844.

for more explanation https://www.geeksforgeeks.org/count-number-increasing-subsequences-size-k/