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
Sliti khaled:
20150926 02:36:28
Nice one :D 

Ayur Jain:
20150828 09:42:08
Nice problem involving DP+BIT :) 

SangKuan:
20150819 05:51:04
why the ans is 2.there only one increasing sequence 1 2 10 

xxbloodysantaxx:
20150712 13:07:49
Such a big silly Mistake !! I was switching the loops ! without even thinking! Nice problem !! 

Pagan Min:
20150624 14:22:47
bit + normalisation


Ahmad Musa:
20150519 10:09:48
I get WA on 10 th case . https://ideone.com/doQLl9


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

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: 