Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TPINCD - Dãy con tăng

 

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

 

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 15,111,992.

 

Example

 

Input:

4 3

1

2

2

10

 

Output:

1

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

 

 


Được gửi lên bởi:dqd
Ngày:2009-11-16
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET
Nguồn bài:Neal Wu

hide comments
2017-10-04 17:56:46
Test yếu vãi, làm sai cũng AC
2016-09-12 04:05:43 nguyenngocanh
:P trâu cũng AC :3
2014-11-22 09:46:03 Lollipop
sao AC trên spoj.com lại k ac trên này nhỉ
2012-11-04 07:53:03 treesseven
ai giải thích giúp mình test đề bài đươc không :|
2011-11-16 12:45:22 trandatbav
sau đúng 2 năm bài được add :D
2009-11-25 10:32:43 pressanykey
Minh cham tren SPOJ thi ACC con o day ket qua sai la sao nhi
2009-11-24 14:56:33 Cảnh Toàn Nguyễn
Bạn nên đọc kỹ đề
"distinct ". Test VD đã khác nhau rồi :D
2009-11-17 08:38:27 AnhDQ
bài này giống INCVN chỉ khác TLE thôi nhỉ :|
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.