Given a sequence of N (1 ≤ N ≤ 10,000) integers S₁, ..., S_N (0 ≤ S_i < 100,000), compute the number of increasing subsequences of S with length K (1 ≤ K ≤ 50 and K ≤ N); that is, the number of K-tuples i₁, ..., i_K such that 1 ≤ i₁ < ... < i_K ≤ N and S_i1 < ... < S_iK.

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 increasing subsequences of S of length K, modulo 5,000,000.

Example

Input:
4 3
1
2
2
10

Output:
2

The two 3-tuples are (1, 2, 4) and (1, 3, 4), both corresponding to the subsequence 1, 2, 10.