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
Rishabh Agrawal: 2020-07-16 11:08:22

Can also be done in O(n*k*logn) using mergesort like technique

yaseenmollik: 2020-03-22 19:05:58

Finally solved it using DP + 2D-BIT

scolar_fuad: 2020-02-27 11:38:55

keep consider that someties BIT can't return value of index 0
finally solved DP+BIT

ankkt16: 2019-10-13 08:35:47

if u r getting WA on test 10 make sure u hv taken care of 0's int the input

abhinav_jain02: 2019-06-14 07:51:18

Note that array S can have zero.

Last edit: 2019-06-14 07:52:48
gabrijel: 2019-03-30 21:56:34

go in 1 AC!

fabijanb: 2019-03-27 21:52:48

solved it using bitset optimization, no wonder I won gold at IOI 2019

linkret: 2019-03-27 16:13:50

i wholeheadedly reccomend this task!

joueur: 2019-01-21 16:41:11

DP+BIT = AC

ayusofayush: 2018-08-15 12:09:34

Probably a good question requires 2-D BIT + DP


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: