Codah ClubTrain. Submit. Improve.
Sign in
English
#0000D3

Incseq

Given a sequence of N (1 ≤ N ≤ 10,000) integers S1 , ..., SN (0 ≤ Si < 1,000,000,000), compute the number of increasing subsequences of S with length K (1 ≤ K ≤ 50 and K ≤ N); that is, the number of K-tuples i1 , ..., iK such that 1 ≤ i1 < ... < iK ≤ N and Si1 < ... < SiK .



InputThe first line of standard input contains the two integers N and K. The following N lines contain the integers of the sequence in order.


OutputPrint a single integer to standard output representing the number of increasing subsequences of S of length K, modulo 500,000,000.



Input:
4 3
1
2
2
10
Output:
2


The two 3-tuples are (1, 2, 4) and (1, 3, 4), both corresponding to the subsequence 1, 2, 10.




Input:
10 3
2
14
7
3
19
4
17
6
19
8
Output:
32

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.