题目描述
A school has N students, numbered from 1 to N. Each student wears a T shirt of some color. The T shirt of the i^th student is of color Ci.
The teachers of the school want to organize a parade. In the parade, there will be some students standing in a straight line in increasing order of height.
The number of students in the line should be atmost M and atleast 1. Your job is to calculate the number of distinct parades that can be organised.
Two parades are said to be distinct if the sequence made by colors of T-shirts worn by students are different.
For each student i, you are given one student Li such that height(Li) < height (i).
Li for the shortest student will be 0.
The height of all students are distinct.
Input:
The first line contains the number of test cases, T.
The first line of each test case contains two space separated integers, N and M.
N lines follow. The i^th line contains two space separated integers, Li and Ci.
Output:
For each test case, output a single line containing the answer of that test case.
Output the answer modulo (10^9+7)
Constraints:
1 ≤ T ≤ 50
1 ≤ M ≤ N ≤ 10^3
0 ≤ Li ≤ N
All Li are distinct
1 ≤ Ci ≤ 1000
Problem Statement in native language: http://hck.re/HRCC50
SAMPLE INPUT
3
2 1
0 1
1 1
2 1
0 1
1 2
2 2
0 1
1 2
SAMPLE OUTPUT
1
2
3
Explanation
In the first test case, there are two students. The student 1 is shorter than student 2.
As M=1, we want only parades with 1 ≤ number of students ≤ 1.
As both students have T shirt of same color, it doesn't matter which student we choose
because both of them have the same T shirt color. So only one parade is possible i.e. [1]
In the second test case, two parades are possible { [1] ,[2] }.
In the third test case, three parades are possible { [1] , [2] and [1,2] }.
NOTE: The sequence of numbers inside [ ] is the sequence of T shirt colors.
输入格式
见题面
输出格式
见题面