**INCDSEQ - Distinct Increasing Subsequences( to do ) no of distinct strictly increasing sequence of length k

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.