The time complexity we need is $O(kn\log n)$. That implies if we have an algorithm, that from the number of $k-1$-long increasing subsequences it counts the number of $k$-long subsequences in $O(n\log n)$ time, we are done. We use prefix sums for storing the actual number of $(k-1)$-long subsequences up to the $l$th element, where the individual entries are the number of (k-1)-long subsequences which ends at $l$th position.
Initialization: The number of 1-long increasing subsequences is 1 for all individual entries.
We read the individual entries of this data structure in $O(2\log n)$
time in the following way: read the prefix up to $l$ and then up to $l-1$ then extract it.
At the beginning of making the $k$-length subsequences we make two empty (all-zero) prefix sums. Then we read the number of $k-1$-long subsequences up to $\pi(1)$. We update one of the table's (denote it $k$-table) $\pi(1)$th entry with the prefix the other (denote it $k-1$-table). Then we update the $k-1$-table's $\pi(1)$th entry with the number of $k-1$-long subsequences ending at $\pi(1)$. We do it also with $\pi(2)$, $\pi(3)$, \dots, $\pi(n)$.
We used only constant number of readings and updates for each $\pi(i)$. So the time complexity is $O(n\log n)$.
When updating the $l$th individual entry of the $k$-table we do the following. We count the number of $k-1$-long subsequences that ends before $\pi(i)$. So that at the ending position of the subsequence the permutation element is smaller than $i$. That is why we need the auxiliary $k-1$-table.