INCDSEQ - Distinct Increasing Subsequences

no tags 

Given a sequence of N (1 ≤ N ≤ 10,000) integers S1, ..., SN (0 ≤ Si < 1,000,000,000), compute the number of distinct increasing subsequences of S with length K (1 ≤ K ≤ 50 and K ≤ N).

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 distinct increasing subsequences of S of length K, modulo 5,000,000.

Example

Input:
4 3
1
2
2
10

Output:
1

The only increasing subsequence of length 3 is 1, 2, 10.


hide comments
pandey101299: 2020-07-15 19:51:41

take care the range of value of s[i]

agrawal117: 2019-07-13 15:59:53

those who are getting WA!!
try this one
input 6 2
3 4 3 4 3 4
output 1

sherlock11: 2018-07-05 09:25:49

use modulo operation wisely.

danish4200: 2017-10-27 17:44:28

very easy cake walk!

sieunhanbom04: 2016-08-08 17:45:43

why C++ 5 is not available on this problem. I got many compile error. Pls add it.

xxbloodysantaxx: 2015-07-12 18:04:55

Wow I am a programmer and I make silly mistakes which irritate me a lot just because the compiler is too stupid to handle it!!

Rang: 2015-06-04 05:07:20

Be mindful of modular Arithmetic :) .

Raghuram: 2014-12-10 19:58:34

what's the answer to
4 2
0 1 0 1
Are the two (0,1) pairs considered the same or different subsequences ?

mindfuck: 2012-06-14 06:08:41

similar problem INCSEQ


Added by:Bin Jin
Date:2008-06-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: CPP
Resource:co-author: Neal Wu