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
Ðứ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. 

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

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