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.