#OJ1801. Time Limit: 1 Sec  Memory Limit: 128 MB

Time Limit: 1 Sec  Memory Limit: 128 MB

Time Limit: 1 Sec  Memory Limit: 128 MB

Description

给定一个长度为n的序列(n <= 100) ,给定m(m <= n),求该序列中有多少值不相同的长度为m的严格上升子序列。

Input

先输入一个T,表明下面会有几组数据。 每组数据先输入一个n,m,表明数组大小和上升子序列长度。 下面一行有n个数代表该数组,且 1<=a[i]<=n;

Output

输出为一行,只需输出上述要求的个数(结果对1000000009取余)。

Sample Input

4
2 2
1 2
4 3
1 2 4 4
5 4
1 2 3 5 4
5 1
1 1 1 2 2

Sample Output

1
1
2
2

HINT

Append Code