Game count

Problem code: MAXGAME

All submissions for this problem are available.

Tug of war is a sport that directly puts two teams against each other in a test of strength. During school days, both Chef Shifu and Chef Po were champions of tug of war. On behalf of restaurant's anniversary, Chef Shifu and Chef Po have decided to conduct a tug of war game for their customers.

Master Chef Oogway has decided the following rules for the game.

  1. Let N be the number of players participating in the game. All of these players would stand in a circle in clock wise direction.
  2. There are an infinite number of long ropes available. When a rope is held by exactly two players, it is termed as bonding.
  3. At least one bonding is necessary to conduct a game.
  4. A player can play against multiple people simultaneously i.e he can have more than one bonding at the same time.
  5. Both members of a pair of players that have a bonding must have the same number of total bondings. That is, if the player A makes bonding with the player B, then the number of total bondings of the player A must be the same as that of the player B.
  6. Bondings should be created in such a fashion that ropes must not intersect each other.
  7. The number of bondings of every player must be no more than K.

Now Master Chef Oogway asked Chef Shifu and Chef Po to find out the number of possible games. Your task is to help them find this number. As this number might become huge, you've to find it modulo (10^14+7). Two games are different iff there is some bonding that is present in only of them.

Input

First line contains T, the number of test cases. Each of T lines contain 2 positive integers N and K separated by a space.

Output

For each test case, output the number of ways to conduct the game modulo 100000000000007 (1014+7) in one line.

Example

Input:
3
3 2
4 0
2 1

Output:
4
0
1
Explanation: For the 1st case, there are 3 players. Let's call them p1, p2, p3. Different games possible are:
Game 1: p1-p2 (numbers of bondings of p1, p2 are 1 ≤ K = 2)
Game 2: p1-p3 (numbers of bondings of p1, p3 are 1 ≤ K = 2)
Game 3: p2-p3 (numbers of bondings of p2, p3 are 1 ≤ K = 2)
Game 4: p1-p2, p1-p3, p2-p3 (numbers of bondings of p1, p2, p3 are 2 ≤ K = 2) For the 2nd test case, we cannot form the game, because K = 0 and hence no player is allowed to make any bonding. As any game must have atleast one bonding, no game is possible here. For the 3rd case, only possible game is:
Game 1: p1-p2 (number of bondings in p1, p2 are 1)

Constraints

1 ≤ T ≤ 10000 0 ≤ N ≤ 10000 0 ≤ K ≤ N

Author: khadarbasha
Tester: laycurse
Editorial http://discuss.codechef.com/problems/MAXGAME
Date Added: 15-05-2012
Time Limit: 3 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

Is it intentional that 10^14

Sumudu @ 2 Aug 2012 05:39 AM
Is it intentional that 10^14 + 7 is not prime? That is certainly not helping

what is that game modulo

remogoku @ 2 Aug 2012 04:07 PM
what is that game modulo 100000000000007 (10^14+7). i'm getting ans for the given test cases.. but what is the need of that game modulo..??

@remogoku for larger values

khad_adm @ 2 Aug 2012 04:54 PM
@remogoku for larger values of N the answer will be high so mod that value with the (10^14+7) and output the result

English in this problem

alcash @ 2 Aug 2012 05:20 PM
English in this problem confuses me a lot. i. Why the ropes are called horizontal when players stand in circle and according to example they can rotate the ropes? iii. I'd consider rewriting this whole item for better readability and to correct numerous grammar mistakes.

@alcash the main intention is

khad_adm @ 2 Aug 2012 06:24 PM
@alcash the main intention is to create a connection with the help of rope in between 2 persons standing in circularly

Do the ropes need to be

al13n @ 2 Aug 2012 09:52 PM
Do the ropes need to be straight line segments or can they be bent and go around the circle (to avoid crossing with the ropes inside the circle)?

@al13n they needs to be

khad_adm @ 2 Aug 2012 10:57 PM
@al13n they needs to be straight

I have to agree with alcash..

triplem @ 4 Aug 2012 07:57 AM
I have to agree with alcash.. the standard of English in this problem (and several others this month) is very very bad and makes the problem very hard to read.

@triplem Please letus know

khad_adm @ 4 Aug 2012 04:23 PM
@triplem Please letus know which part the problem confusing you So that we can make the problem more clear ..

"holded" nice one

damians @ 4 Aug 2012 08:06 PM
"holded" nice one

Do the players have to stay

tehqin @ 4 Aug 2012 08:43 PM
Do the players have to stay in place in order or can they change places (while still standing in the circle) to help resolve crossing issues.

@tehqin Players needs to be

khad_adm @ 4 Aug 2012 10:10 PM
@tehqin Players needs to be stay in place

if n=4 and k=1,is p1-p2 p3-p4

darkgt @ 5 Aug 2012 12:30 AM
if n=4 and k=1,is p1-p2 p3-p4 a legal game?

@darkgt yes it is a legal

khad_adm @ 5 Aug 2012 12:11 PM
@darkgt yes it is a legal game because 1.both ropes are non intersecting(p1,p2,p3,p4 are standing in a circle) 2.No of bondings of p1=p2=1(<=k) And also p3=p4=1(<=k)

We have updated the problem

admin @ 5 Aug 2012 11:36 PM

We have updated the problem statement. Regret the inconvenience caused.

For n=5 k=2

prathyusha1 @ 7 Aug 2012 12:21 AM
For n=5 k=2 (1,2),(3,4),(4,5),(3,5) is a legal game..??

@prathyusha1 it's a valid

khad_adm @ 7 Aug 2012 02:38 PM
@prathyusha1 it's a valid game because 1. No of bondings in 1-2 ( for player1-1 and for player2-1)<=K(2) 2.And No of bondings in 3-4 4-5 3-5 ( for player 3 - 2 and for player4-2 and for player5-2) <=K(2) 3.All ropes are non intersecting

@admin : can we have more

phantom11 @ 7 Aug 2012 10:38 PM
@admin : can we have more than 1 bonding with the same player ? i.e. is answer for 2 2 is 2 or 1??

@phantom11 Yes we can have

khad_adm @ 8 Aug 2012 12:25 AM
@phantom11 Yes we can have more than 1 bonding with the same player iff the players who hold the rope must have same number of bondings...

@khad_adm: Could I ask you a

tyrant @ 8 Aug 2012 03:58 AM
@khad_adm: Could I ask you a quick question about the bonding condition? Suppose we have: p1-p2-p3-p4-p1 and p5-p6, does it count as 2 + 1 = 3 bonding? Thanks in advance.

I think answer for 2 2 is 1.

imgpsingh @ 8 Aug 2012 09:35 AM
I think answer for 2 2 is 1. If its 2 then the answer for 3 2 must be greater than 4. Please confirm the answer for the input where n=2 and k=2... Thanks.

@imgpsingh for n=2 and k=2

khad_adm @ 8 Aug 2012 02:01 PM
@imgpsingh for n=2 and k=2 the possible arrangement is p1-p2 (bondings(p1)-1 bondings(p2)-1) and no more arrangement is possible so ans is 1

@admins : I want to know how

phantom11 @ 10 Aug 2012 07:00 AM
@admins : I want to know how the solutions are judged in codechef..Does it break as soon as it gets a wrong answer or a runtime error on a test case or keep checking all the test cases first and if it fits in time then tell the verdict (WA,RE,AC etc )else TLE ...

@khad_adm Is p1-p2-p3-p4-p1

kohyatoh @ 10 Aug 2012 03:42 PM
@khad_adm Is p1-p2-p3-p4-p1 (formally, p1-p2, p2-p3, p3-p4, p4-p1) really an invalid arrangement? I think No.of boundings of p1, p2, p3, p4 are all 2 so it's a valid arrangement.

@kohyatoh @tyrant .sorry for

khad_adm @ 10 Aug 2012 09:55 PM
@kohyatoh @tyrant .sorry for the previous mistake P1-P2-P3-P4-P1 is a valid arrangement because no of bondings of P1,P2,P3,P4 are 2 .

SUCCESSFUL SUBMISSIONS


Fetching successful submissions