[Hidden]
#### 1238. I. LIS Number

#### Description

Let A be a sequence of integers. The LIS Number of A is the smallest positive integer L such that A can be obtained by concatenating L strictly increasing sequences. For example, the LIS Number of A = {1, 4, 4, 2, 6, 3} is 4, since we can obtain A as {1, 4} + {4} + {2, 6} + {3}, and there is no way to create A by concatenating 3 (or fewer) strictly increasing sequences. The LIS Number of a strictly increasing sequence is 1.

The Problem:

You are given a sequence of length N and an integer K. You want to transform the given sequence into a sequence with LIS Number K. The only operation you are allowed to do is to delete 0 or more numbers from the original sequence. Count how many ways you can do that. Two ways are different if the set of removed numbers (their indices/positions) are different.

#### Input

The first input line contains a positive integer, t, indicating the number of test cases. First line of each test case consists of two integers N (1 ≤ N ≤ 50,000) and K (1 ≤ K ≤ 10). The second line contains N integers of the sequence (separated by a single space). These integers will be between 0 and 100000, inclusive.

#### Output

For each test case, output the number of ways you can transform the given sequence of length N into a sequence with LIS Number K. Since the number of ways can be too large, output the result modulo 1,000,000,007.

#### Samples

#### Source

UCF2013

The Problem:

You are given a sequence of length N and an integer K. You want to transform the given sequence into a sequence with LIS Number K. The only operation you are allowed to do is to delete 0 or more numbers from the original sequence. Count how many ways you can do that. Two ways are different if the set of removed numbers (their indices/positions) are different.

Time Limit: | 3000MS (C/C++,Others×2) |

Memory Limit: | 128MB (C/C++,Others×2) |

Special Judge: | No |

AC/Submit: | 1 / 1 |

Tags: |