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
raj_394: 2015-11-13 05:51:05

Nice problem for understanding Binary Index Trees. Advice is to understand BIT properly before doing this one.. go through this link for getting familiar to BIT https://www.hackerearth.com/notes/binary-indexed-tree-made-easy-2/ .... happy coding :)

Karun : 2015-10-25 14:36:25

If you have a complexity of ~ O(n*k*log(k*100000)) and you're still getting a TLE
-> optimize modulus operations
-> normalize the input array

Sliti khaled: 2015-09-26 02:36:28

Nice one :D

Ayur Jain: 2015-08-28 09:42:08

Nice problem involving DP+BIT :)

SangKuan: 2015-08-19 05:51:04

why the ans is 2.there only one increasing sequence 1 2 10

xxbloodysantaxx: 2015-07-12 13:07:49

Such a big silly Mistake !! I was switching the loops ! without even thinking! Nice problem !!

Pagan Min: 2015-06-24 14:22:47

bit + normalisation
nice one :D

Ahmad Musa: 2015-05-19 10:09:48

I get WA on 10 th case . https://ideone.com/doQLl9
plz help

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 !!


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: