INCDSEQ  Distinct Increasing Subsequences
Given a sequence of N (1 ≤ N ≤ 10,000) integers S_{1}, ..., S_{N} (0 ≤ S_{i} < 1,000,000,000), compute the number of distinct increasing subsequences of S with length K (1 ≤ K ≤ 50 and K ≤ N).
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 distinct increasing subsequences of S of length K, modulo 5,000,000.
Example
Input: 4 3 1 2 2 10 Output: 1
The only increasing subsequence of length 3 is 1, 2, 10.
hide comments
agrawal117:
20190713 15:59:53
those who are getting WA!!


sherlock11:
20180705 09:25:49
use modulo operation wisely. 

danish4200:
20171027 17:44:28
very easy cake walk!


sieunhanbom04:
20160808 17:45:43
why C++ 5 is not available on this problem. I got many compile error. Pls add it. 

xxbloodysantaxx:
20150712 18:04:55
Wow I am a programmer and I make silly mistakes which irritate me a lot just because the compiler is too stupid to handle it!! 

Rang:
20150604 05:07:20
Be mindful of modular Arithmetic :) . 

Raghuram:
20141210 19:58:34
what's the answer to


mindfuck:
20120614 06:08:41
similar problem INCSEQ 
Added by:  Bin Jin 
Date:  20080622 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: CPP 
Resource:  coauthor: Neal Wu 