BOOKWORM - Kuchu the Bookworm

In this problem, you’ll be helping a little bookworm, Kuchu.

Recently “Omuk book shop” has announced a huge sale on various books. Being a bookworm, Kuchu could not miss this opportunity and went there immediately!

When reached there, she noticed that conditions of the sale are:

  1. One must buy exactly B books to get the discount.
  2. Maximum number of pages in any book is no more than 100.

As she wants to read as much as possible, Kuchu wants to get maximum number of pages satisfying the conditions above. Now she is wondering if there are N books in the store, how many different ways are there to choose exactly B books so that the number of pages is maximum possible.

Not all books are interesting to little kids, so you are given two information about each book-

  1. Number of pages P.
  2. Interest value V. V is 1 if the book is interesting for kids and 0 otherwise.

Input

First line contains an integer T, the number of test cases.

For each test case, the first line contains two integers N and B as mentioned above. Next N lines contain two integers each Pi and Vi, number of pages and interest factor of ith book.

1 ≤ T ≤ 25

1 ≤ N ≤ 100,000

1 ≤ B ≤ N

1 ≤ Pi ≤ 100

0 ≤ Vi ≤ 1

Output

For each test case, print one integer, the number of different ways to choose exactly B interesting books from those N books so that the number of pages is maximum possible. As result can be pretty large, print it modulo 1,000,000,007 (10^9+7).

Example

Input:

2
2 1
2 0
3 0
5 3
10 0
5 1
2 1
2 1
2 1

Output:

0
3


Added by:Evan
Date:2016-04-27
Time limit:0.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
Resource:From NHSPC 2016 Final Round.http://www.nhspc.org/

hide comments
2019-07-26 20:05:40
Useless TL prevents AC in Python. Downvote.
2017-07-11 00:30:25
Can anyone give a test case?
2016-09-23 07:58:55 Evan
@DHEERAJ: Don't know why you got TL, might be SPOJ's issue, now your submission get WA.
2016-05-12 11:09:32 DHEERAJ KUMAR
@Evan : submission id 16903603. Can u Please check why am i getting TLE. Complexitiy O(T*n)
2016-05-10 13:13:29 Evan
@Vikneshwar, I've seen your submission and it's not O(N) of course. Try optimizing :)
2016-04-30 19:08:35 Vikneshwar E
@Evan : Submission ID 16845370. Can you please check why I am getting TLE for this solution. Mine is O(N) only.
2016-04-28 11:51:15 Vipul Srivastava
Ya C++4.3.2 is giving TLE
2016-04-28 11:42:13 Evan
@ (^_^) : That's strange! Your solution works as intended when submitted in C++14. There might be some issue with C++.
2016-04-28 10:22:47 Vipul Srivastava
O(B) algo gives TLE since B can be upto N so that is the time to scan the input.
@Evan please help.
2016-04-28 10:18:38 (^_^)
I am only scanning the inputs and printing 0 but still giving TLE. Is there something wrong with the question?

Finally Got accepted C++ has some issue here.

Last edit: 2016-04-28 12:44:55
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.