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
Sunil: 2015-04-18 13:08:32

Trying to do multiple cases as in tutorial problem eldorado costed a lot TLE :(

arp_ee: 2015-03-30 17:18:26

nice problem !! learnt a lot !!

Siddharth Varia: 2015-03-28 15:52:02

I am also getting wrong answer. My code is at https://ideone.com/cb4q3X. Any help will be appreciated.

super man: 2015-03-19 18:37:00

very easy......:(
piece of cake.
accept in first time...
my 50th

Last edit: 2015-03-19 18:41:58
Ðứ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.


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: