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
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
aayush: 2011-08-04 17:50:35

DP???

Fahim Zubayer: 2011-05-14 02:35:50

DO REMEMBER to handle the zero :( Cost me a lot of TLE's

Nikhil Garg: 2010-05-20 11:52:41

INCDSEQ is a similar problem.


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