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
ayusofayush: 2018-08-15 12:09:34

Probably a good question requires 2-D BIT + DP

karan_yadav: 2018-08-05 08:42:30

A really good problem!
Hint:
1. Follow the bottom-up approach. ie for each new element x calculate the j-length increasing subsequence (1 <= j <= k) that can be formed with elements up to x.
2. For storing the above task, you'll need a data structure. The first thing that comes to mind is a double dimension array. Though it'll work it'll exceed the time limit. Why? because we'll be reading as well as updating a range. Which take linear time in DDA. So we need to find a faster way.
3. 2-D BIT is all you need

be1035016: 2018-07-14 09:29:56

nice concept...used 50 BITEES;) (though not required)

Last edit: 2018-07-14 09:30:24
jacobian_det: 2018-06-26 09:52:39

my 100th on spoj :)

sinersnvrsleep: 2018-04-24 13:25:23

look for the tricky case caused few tles
anyways learnt a lot thanks Neal Wu

up79: 2017-06-21 08:38:18

2-D BIT is passing ! ac .

giorgosgiapis: 2017-04-04 11:26:29

Nice problem! Normalization not needed here. ACed with dp + BIT.
Just take care of zeroes.

Last edit: 2017-04-04 11:27:41
iam_ss: 2017-02-20 22:25:58

DP + BIT ... AC

deerishi: 2016-08-31 00:28:48

Segment tree + DP with FAST I/O also accepted!

Nguyen Cuong: 2016-05-05 10:52:10

dp + BIT ^^


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: