MYQ5 - The Nerd Factor

Prof.Venky handles Advanced Topics in Algorithms course for a class of 'n' students. He is always known for his unsolvable question papers. Knowing that it is impossible to pass his subject in a fair manner, one of the students of his class, Vishy, finds out from his seniors that Prof.Venky won't be able to find out if at least 'k' students together discuss and write the answers and thereby all of them can pass. Hence they decide to divide the whole class into a number of groups so that everyone passes. But all the students are fighting over forming the groups. So Puppala, one of the nerdy students in the class, decides  that he will compute all possible ways that they can form the groups and number them, and finally choose one of those numbers at random and go ahead with that way. Now it is your duty to help Puppala find the number of  ways that they can form such groups. 

Pupalla is incapable of reading big numbers, so please tell him the answer modulo 10^9+7.

Input

The first line contains the number of test case t(1<=t<=10^6).
Followed by t lines for each case.
Each test case contains two integers 'n' and 'k' separated by a space(1<=k,n<=1000)

Output

For each test case, print a single line containing one positive integer representing the number of ways modulo 10^9+7 .

Example

Input:
3 
2 1
4 2
6 2 Output: 2
2
4

Added by:jack(chakradarraju)
Date:2012-02-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Bytecode 2012

hide comments
2023-08-21 19:44:54
can anyone give me a corner case with test case of this problem,please?
2015-09-13 19:06:21 Pranav Rai
@admn - Getting TLE , submission code -http://www.spoj.com/submit/MYQ5/id=15115385

I am using precomputation.
2015-07-13 13:11:48 Ankit
Question is quite ambigous, please clarify that you dont want number of ways , but number of ways of groups without considering the elements inside the group

Last edit: 2015-07-13 13:12:53
2015-05-30 11:09:10 Pulkit Singhal
@Rahul : O(n^2) DP is acceptable
2015-05-24 08:50:17 Dushyant Singh
Is a group of 4 and 2 and a group of 2 and 4 counted as different?
2014-09-26 21:18:07 Rahul Jain
Can anyone please tell me the time complexity it will accept?
I used DP with O(n^2)-->TLE

Last edit: 2014-09-26 21:22:33
2013-11-01 20:46:00 Apoorv Jindal
Why have all students been treated as identical? Either the problem statement should be changed or the test suite.
2013-06-22 15:50:09 Man Mohan Mishra
nice problem !! :)
2013-02-16 11:40:46 (Tjandra Satria Gunawan)(曾毅昆)
WOW! 0.70s without fast I/O, and 0.17s with fast I/O? (o_O)
first place for now ;-)
2012-12-12 04:22:27 Paul Draper
@Mitch Schwartz is right. If you were to ask me how many ways I could divide Bob, Sue, Joey, and Mary into groups so that every group has at least two, I would answer 4.
This problem, however, asks for the answer 2. Please add this clarification to the problem.

A couple more test cases:
2
1 1000
1000 1

0
709496666
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.