## 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}.

### 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 10Output:2

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

Added by: | Neal Wu |

Date: | 2008-06-20 |

Time limit: | 0.143s-0.286s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ERL JS-RHINO |

Resource: |