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
Sunil:
20150418 13:08:32
Trying to do multiple cases as in tutorial problem eldorado costed a lot TLE :( 

arp_ee:
20150330 17:18:26
nice problem !! learnt a lot !! 

Siddharth Varia:
20150328 15:52:02
I am also getting wrong answer. My code is at https://ideone.com/cb4q3X. Any help will be appreciated. 

super man:
20150319 18:37:00
very easy......:(


Ðức Anh:
20141203 16:54:10
If you get TLE with complexity less than O(n*k*log(k*100000)) you should do this optimisation.


octopus:
20141021 22:26:05
getting wa on 10th test case. please help. Handled 0 as well. some large test cases. i m using space 100000*51. could it be any problem. Last edit: 20141021 22:40:08 

ISHANI:
20140624 07:04:19
#humble_coder


Himank Agrawal:
20140519 12:33:42
Soln with complexity O(n*k*2*log(100000)) giving TLE... Why? 

humble_coder:
20140401 10:05:36
can someone provide me with some test cases.


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. 
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: 