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
gabrijel:
20190330 21:56:34
go in 1 AC! 

fabijanb:
20190327 21:52:48
solved it using bitset optimization, no wonder I won gold at IOI 2019 

linkret:
20190327 16:13:50
i wholeheadedly reccomend this task! 

joueur:
20190121 16:41:11
DP+BIT = AC 

ayusofayush:
20180815 12:09:34
Probably a good question requires 2D BIT + DP 

karan_yadav:
20180805 08:42:30
A really good problem!


be1035016:
20180714 09:29:56
nice concept...used 50 BITEES;) (though not required) Last edit: 20180714 09:30:24 

jacobian_det:
20180626 09:52:39
my 100th on spoj :) 

sinersnvrsleep:
20180424 13:25:23
look for the tricky case caused few tles


up79:
20170621 08:38:18
2D BIT is passing ! ac .

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: 