Supto is a student at Daffodil International University (DIU). He is also a mentor for school students in programming. Currently, he is excited because there will be a programming contest held among school-level students. However, he is a little bit worried because he needs to form a team from his students to participate in this contest. He wants the best team possible. He has students' information such as Name, Class, and Score. The score represents the performance rating of each student. Unfortunately, the information is not well-organized. Supto needs the information sorted, where the student with the highest score comes before the one with the lower score. In case of a tie in scores, the student with the higher class comes before the one with the lower class. If there is still a tie, the student with the alphabetically earlier name comes before the one with the later name. With the sorted data, Supto can easily select his students to participate in the programming contest.

Supto also wants to know how many ways he can form teams (a team must have at least one student) so that their total score adds up to K. Help Supto!

Input

The input starts with an integer T denoting the number of test cases. The next line contains N and K. Then, in the following N lines, each line contains a string S_i denoting the i^th student's name, an integer C_i denoting the i^th student's class, and an integer SR_i denoting the i^th student's score.

Output

For each test case, print the sorted students with their class and score. After that, print the following line: "Number Of Ways Teams Can Be Formed = P" without quotes, where P denotes the number of ways teams can be formed such that the total score of the teams is equal to K. The value of P can be large, so print the value of P modulo 100000007.

Constraints

1 ≤ T ≤ 100 (Number of test cases)

1 ≤ N ≤ 1000 (Number of students)

1 ≤ K ≤ 100000

1 ≤ |S| ≤ 50 (Length of each student's name)

1 ≤ C ≤ 10 (Class number)

0 ≤ SR ≤ 100 (Score of the student)

Note: There can be multiple students with the same name in the same class and even having the same score.

Example

Input:

2
3 5
a 5 5
aa 5 6
aaa 5 5
5 8
alim 3 1
rajjo 3 3
alom 3 9
rafiq 3 5
biplob 3 8

Output:

aa 5 6  
a 5 5  
aaa 5 5  
Number Of Ways Teams Can Be Formed = 2  
alom 3 9  
biplob 3 8  
rafiq 3 5 
rajjo 3 3  
alim 3 1  
Number Of Ways Teams Can Be Formed = 2

Explanation of 2nd Test Case

Way 01 to form a team so that their score adds up to 8

Students = biplob

Sum of Score = 8

Way 02 to form a team so that their score adds up to 8

Students = rafiq, rajjo

Sum of Scores = 5 + 3 = 8

Hence, Number of Ways Teams Can Be Formed = 2

Problem Setter: Abdul Alim, Full Stack Web Developer, Bangladesh