VECTAR12 - Garden of Mangu

no tags 

Mangu bought a new garden for himself. The garden is shown below in the image. The garden is semi infinite i.e. infinite in two directions (+x direction and +y direction). Garden's square cells are indexed as in the diagram. Changu comes to visit Mangu and see his garden. He is standing initially on (0, 0). From a particular cell he can travel in 8 directions if possible. His task is to go from (0, 0) to (n, k) in n steps. Your task is to calculate the number of possible paths he can take.

Diagram

Input

The first line contains the number of test cases, T. The next T lines contain two integers n and k separated by a single space.

Output

You have to print the number of possible paths modulus 1000000007.

Example

Input:
2
1 1
2 0

Output:
1
2

Explanation

The possible paths for two case are shown below:

Case 1:

case 1

 

Case 2:

case 2

 

Constraints:

T<10^5

0<=N<7000

0<=K<=N


hide comments
Rafail Loizou: 2021-05-10 19:01:25

@dwij28 I think that it was done by purely using math rather than DP. I tried implementing such solution but the thing is I don't know if the array of the multiplicative inverses from 0 to 7000 would fit in the 50K bytes limit that the code has and also allow me to code the solution. Because if you have the multiplicative inverses ready then it becomes a linear solution. I did a rough estimate as to how many characters it would need which is 7000 * 10 so 70K bytes of code, thus I was discouraged from trying such a solution. Also the computation of such an array would take a lot of time.

P.S. Unless there are some other wicked mafs, that I don't recall or could not even fathom, which would accelerate this.

Last edit: 2021-05-10 19:03:53
ks1999: 2016-10-08 12:14:26

ez dp

Last edit: 2020-04-18 18:37:21
dwij28: 2016-10-07 00:38:47

Got a few TLE's, a few WA (maybe due to case (0, 0)) but got AC in the end (2.88 seconds). :) By the way, the top ranked solution by @Min_25 is 0.06 seconds & 4M of memory. Just brilliant. I have no clue how to optimize the solution to that extent. Hats off to the genius @Min_25.

Min_25: 2016-07-17 11:05:12

When the problem has some images, please upload them to http://www.spoj.com/uploads/.

Re: Thanks, I will make sure. I didn't know we could do that. More convenient :)

Last edit: 2016-07-17 11:43:14
icm2015007: 2016-07-15 19:14:24

AC!

Last edit: 2016-07-20 20:28:50
Piyush Kumar: 2016-07-14 12:37:28

Please mention anything that is not clear from the problem statement.


Added by:Piyush Kumar
Date:2016-07-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own Problem