TPINCD - Dãy con tăng
Giới hạn- Thời gian: 0.142s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
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.
- Người up: dat1511
- Nguồn bài: Neal Wu