SP27375 VECTAR12 - Garden of Mangu

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. 

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.

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