INCDSEQ - Distinct Increasing Subsequences

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.


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

hide comments
2024-07-15 17:25:42
have any one have test that can fall my code ?
<snip>
[Simes]: this is not the place to debug code. Please use the forum.


Last edit: 2024-07-15 22:34:01
2020-07-15 19:51:41
take care the range of value of s[i]
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
2018-07-05 09:25:49
use modulo operation wisely.
2017-10-27 17:44:28
very easy cake walk!
2016-08-08 17:45:43
why C++ 5 is not available on this problem. I got many compile error. Pls add it.
2015-07-12 18:04:55 xxbloodysantaxx
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!!
2015-06-04 05:07:20 Rang
Be mindful of modular Arithmetic :) .
2014-12-10 19:58:34 Raghuram
what's the answer to
4 2
0 1 0 1
Are the two (0,1) pairs considered the same or different subsequences ?
2012-06-14 06:08:41 mindfuck
similar problem INCSEQ
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.