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
Ðức Anh: 2014-12-03 16:54:10

If you get TLE with complexity less than O(n*k*log(k*100000)) you should do this optimisation.
Instead of doing

(a+b)%mod


do

int c = (a+b);
if ( c >= mod ) c -= mod;

octopus: 2014-10-21 22:26:05

getting wa on 10th test case. please help. Handled 0 as well. some large test cases. i m using space 100000*51. could it be any problem.

Last edit: 2014-10-21 22:40:08
ISHANI: 2014-06-24 07:04:19

#humble_coder
if u r getting wrong ans at 10th test case,it's because of mod

Himank Agrawal: 2014-05-19 12:33:42

Soln with complexity O(n*k*2*log(100000)) giving TLE... Why?

humble_coder: 2014-04-01 10:05:36

can someone provide me with some test cases.
i have tried several test cases and i am getting right ans. i handled the 0 as well but am getting WA on spoj for the 10th test case.
i think its because of mod
ideone link
http://ideone.com/bqtU2P

Last edit: 2014-04-01 10:16:23
Curiosa: 2014-03-10 15:42:32

Though, some of you who get TLE think that the problem is in the complexity of your algorithm, test your solution on test which includes 0.

vinay guthal: 2014-02-21 10:40:52

Nice question :)

Akhilesh Anandh: 2014-02-04 20:56:07

Nice one..

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... :(


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: