INCSEQ - Increasing Subsequences


Given a sequence of N (1 ≤ N ≤ 10,000) integers S1, ..., SN (0 ≤ Si < 100,000), compute the number of increasing subsequences of S with length K (1 ≤ K ≤ 50 and K ≤ N); that is, the number of K-tuples i1, ..., iK such that 1 ≤ i1 < ... < iK ≤ N and Si1 < ... < SiK.

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 3-tuples are (1, 2, 4) and (1, 3, 4), both corresponding to the subsequence 1, 2, 10.


hide comments
Ankit Chaudhary: 2014-01-12 12:03:30

what will be output for :
3 2
1 1 5

1 or 2??
I am getting WA : any tricky test case.

DIBYA TANOY: 2013-08-02 09:00:26

Yeah, the zero... :(

Abo Hasan: 2013-03-12 18:41:10

I really wonder how is it solved in 0 seconds, while my solution is 4.6 !

Gegham: 2012-10-17 12:26:27

myprog works in my test I think the problem is about modulo can anybody give me any testdata or advice ? DDDDDDDDD

Tornike Mandzulashvili: 2012-08-29 16:37:03

@სვანიძე
n*k*log(10000) shi dawere intervalta xe aage shekumshul masivze

patapatapatapon!: 2012-04-01 12:38:53

what does 'internal error' mean? i got this result from my submission for this problem with id 6765418

სვანიძე: 2012-03-14 15:09:52

Myprog works in o(n*k*log(100000)) and it returns TLE help :(
RE:Well, the official solution works exactly in that time, I couldn't think of a better one, you must be having a big constant.

Last edit: 2012-03-14 16:05:19
ulasuevoli: 2012-01-10 12:02:29

My code fails for
4 1
1 2 3 4
Answer should be 4
but my AC answer is 0
I think the author should include this case . :P

Pranay: 2011-12-18 16:43:52

can try ELDORADO in tutorial..

Vlade087: 2011-09-02 15:28:21

anybody can give me some testdata

Last edit: 2011-09-02 17:16:16

Added by:Neal Wu
Date:2008-06-20
Time limit:0.143s-0.286s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource: