A race timing system records n checkpoint values in course order. Count the number of ways to choose exactly k positions p_1 < p_2 < ... < p_k such that the chosen values are strictly increasing (value[p_1] < value[p_2] < ... < value[p_k]). That is, count the strictly increasing subsequences of length exactly k. Two choices differ if they use different sets of positions, even when the values match.
Input format
Line 1: two integers n and k.
Line 2: n space-separated integers, the checkpoint values in course order.
Output format
A single integer: the number of strictly increasing length-k subsequences.
Constraints
- 1 <= n <= 60
- 1 <= k <= n + 1
- -1000000000 <= value <= 1000000000
- The answer fits in a signed 64-bit integer.