SP2815 INCSEQ - Increasing Subsequences

Given a sequence of N (1 ≤ N ≤ 10,000) integers S $ _{1} $ , ..., 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 $ _{1} $ , ..., i $ _{K} $ such that 1 ≤ i $ _{1} $ < ... < i $ _{K} $ ≤ N and S $ _{i1} $ < ... < S $ _{iK} $ .

The first line contains the two integers N and K. The following N lines contain the integers of the sequence in order.

Print a single integer representing the number of increasing subsequences of S of length K, modulo 5,000,000.