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
giorgosgiapis:
20170404 11:26:29
Nice problem! Normalization not needed here. ACed with dp + BIT.


iam_ss:
20170220 22:25:58
DP + BIT ... AC 

deerishi:
20160831 00:28:48
Segment tree + DP with FAST I/O also accepted! 

Nguyen Cuong:
20160505 10:52:10
dp + BIT ^^ 

ghost_wire:
20160225 20:07:09
what will be the output for 4,3


minhthai:
20160125 04:21:31
oh man the mod costs me too many WA :(( 

GAURAV CHANDEL:
20151230 18:09:20
Cool ... very cool problem.... 

Ankit Sultana:
20151212 18:40:19
Check the modulus, it's not 10^9+7 

raj_394:
20151113 05:51:05
Nice problem for understanding Binary Index Trees. Advice is to understand BIT properly before doing this one.. go through this link for getting familiar to BIT https://www.hackerearth.com/notes/binaryindexedtreemadeeasy2/ .... happy coding :) 

Karun :
20151025 14:36:25
If you have a complexity of ~ O(n*k*log(k*100000)) and you're still getting a TLE

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: 