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.


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:

hide comments
2015-06-24 14:22:47 Pagan Min
bit + normalisation
nice one :D
2015-05-19 10:09:48 Ahmad Musa
I get WA on 10 th case . https://ideone.com/doQLl9
plz help
2015-04-18 13:08:32 Sunil
Trying to do multiple cases as in tutorial problem eldorado costed a lot TLE :(
2015-03-30 17:18:26 arp_ee
nice problem !! learnt a lot !!
2015-03-28 15:52:02 Siddharth Varia
I am also getting wrong answer. My code is at https://ideone.com/cb4q3X. Any help will be appreciated.
2015-03-19 18:37:00 super man
very easy......:(
piece of cake.
accept in first time...
my 50th

Last edit: 2015-03-19 18:41:58
2014-12-03 16:54:10 Ðức Anh
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;
2014-10-21 22:26:05 octopus
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
2014-06-24 07:04:19 ISHANI
#humble_coder
if u r getting wrong ans at 10th test case,it's because of mod
2014-05-19 12:33:42 Himank Agrawal
Soln with complexity O(n*k*2*log(100000)) giving TLE... Why?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.