parade-4

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.

Source: hackerearth | Difficulty: HARD


Solutions: