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
up79: 2017-06-21 08:38:18

2-D BIT is passing ! ac .

giorgosgiapis: 2017-04-04 11:26:29

Nice problem! Normalization not needed here. ACed with dp + BIT.
Just take care of zeroes.

Last edit: 2017-04-04 11:27:41
iam_ss: 2017-02-20 22:25:58

DP + BIT ... AC

deerishi: 2016-08-31 00:28:48

Segment tree + DP with FAST I/O also accepted!

Nguyen Cuong: 2016-05-05 10:52:10

dp + BIT ^^

ghost_wire: 2016-02-25 20:07:09

what will be the output for 4,3
1,2,4,10

minhthai: 2016-01-25 04:21:31

oh man the mod costs me too many WA :((

GAURAV CHANDEL: 2015-12-30 18:09:20

Cool ... very cool problem....

Ankit Sultana: 2015-12-12 18:40:19

Check the modulus, it's not 10^9+7

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 :)


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: