INCSEQ  Increasing Subsequences
Given a sequence of N (1 ≤ N ≤ 10,000) integers S_{1}, ..., S_{N} (0 ≤ S_{i} < 100,000), compute the number of increasing subsequences of S with length K (1 ≤ K ≤ 50 and K ≤ N); that is, the number of Ktuples i_{1}, ..., i_{K} such that 1 ≤ i_{1} < ... < i_{K} ≤ N and S_{i1} < ... < S_{iK}.
Input
The first line contains the two integers N and K. The following N lines contain the integers of the sequence in order.
Output
Print a single integer representing the number of increasing subsequences of S of length K, modulo 5,000,000.
Example
Input: 4 3 1 2 2 10 Output: 2
The two 3tuples are (1, 2, 4) and (1, 3, 4), both corresponding to the subsequence 1, 2, 10.
hide comments
Curiosa:
20140310 15:42:32
Though, some of you who get TLE think that the problem is in the complexity of your algorithm, test your solution on test which includes 0. 

vinay guthal:
20140221 10:40:52
Nice question :)


Akhilesh Anandh:
20140204 20:56:07
Nice one.. 

Ankit Chaudhary:
20140112 12:03:30
what will be output for :


DIBYA TANOY:
20130802 09:00:26
Yeah, the zero... :(


Abo Hasan:
20130312 18:41:10
I really wonder how is it solved in 0 seconds, while my solution is 4.6 ! 

Gegham:
20121017 12:26:27
myprog works in my test I think the problem is about modulo can anybody give me any testdata or advice ? DDDDDDDDD 

Tornike Mandzulashvili:
20120829 16:37:03
@სვანიძე


patapatapatapon!:
20120401 12:38:53
what does 'internal error' mean? i got this result from my submission for this problem with id 6765418 

სვანიძე:
20120314 15:09:52
Myprog works in o(n*k*log(100000)) and it returns TLE help :(

Added by:  Neal Wu 
Date:  20080620 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 
Resource: 