Devu is learning Combinatorics in his college. He find it very interesting to calculate number of ways of going to point (c,d) from point (a,b) in co-ordinate plane. We can take horizontal and vertical steps only and can not visit at a point twice. In a step, you can move one unit only. We have to reach to the point(c,d) from the point (a,b) using abs(a-c)+ abs(b-d) steps only.

Devu has two sets of points. Set A contains points having X co-ordinate 0 and Y co-ordinates varying from 1 to N(both inclusive). Set B contains points having X co-ordinate K and Y co-ordinates varying from 1 to N(both inclusive). Both sets contains N number of integral points. He wants to calculate the sum of number of ways to going to the each point of set B from the each point of set A .

As the answer can be large, print it modulo 1000000007.

Input

First of all this question has many concpets intermingled

(1) Hockey stick theorem

(2) inverse modulo

(3) travelling a grid

We are given two sets of points X and Y (described above) in 2-D grid, and we have to find the number of ways to move from all points in X to all points in Y using minimum number of steps. Note that only vertical and horizontal travelling is allowed and since we have to move from one point to another in minimum number of steps, we cannot visit a point twice.

The number of shortest paths from (0,0) to (m,n) in 2D grid is (m+nn). Using this result, in this problem, we essentially have to find the following term in which the first summation loops over the points in set X and second summation loops over the points in set Y.

S=∑i=1n∑j=1n(|j−i|+kk)

Now the absolute value of j−i is a bug and we have to some how get rid of that absolute sign. The easiest way to do so is to consider the case when j≥i and j<i . So, for any point i in set X, divide the points in set Y into 3 parts - lower y-points , upper y-points and y-point which is at the same level. Note that the upper and lower point cases are symmetrical. Hence, S can be written as follows

S=2∑i=1n∑j=in(j−i+kk)−n

Now the only thing which is left, is to calculate ∑ni=1∑nj=i(j−i+kk).

∑i=1n∑j=in(j−i+kk)=∑i=1n∑j=kn−i+k(jk)=∑i=1n(n−i+k+1k+1) Hockey Stick Identity =∑i=k+1n+k(ik+1)=(n+k+1k+2)  Hockey Stick Identity 

The binomial terms can be calculated in O(1) time if we have precomputed the factorial and inverse factorial. Hence, answer for every test case can be computed in O(1) time.

The hockey stick theorem is a very important theorem in combinatorics, to read more about it

http://math.stackexchange.com/questions/74844/induction-proof-concerning-a-sum-of-binomial-coefficients-sum-j-mn-binomj

after that the answer is simply 2*ncr(n+k+1,k+2)-n

But to take care of moding we needed to find the inverse modulo which is given as 

                                 power(value,m-2) where m=mod value this is derived from fermat little theorem 

To know more

http://math.stackexchange.com/questions/25390/how-to-find-the-inverse-modulo-m

The code goes here

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

ll fact[2000010];

#define m 1000000007

ll power(int val, int y)

{

if(y==0)

return 1;

ll temp=power(val,y/2);

if(y%2==0)

return (temp*temp)%m;

else

{

return (((temp*temp)%m)*val)%m;

}

}

ll inv(int n)

{

   return power(n,m-2);

}

ll C(int n,int r)

{

   ll num1=fact[n];

   ll num2=inv(fact[r]);

   ll num3=inv(fact[n-r]);

   ll ans=(num1*num2)%m;

   ans=(ans*num3)%m;

   return ans;

}

int main()

{

int t;

cin>>t;

fact[0]=1;

for(int i=1;i<=2000003;i++)  

fact[i]=(i*fact[i-1])%m;

while(t--)

{

ll n,k;

scanf("%lld %lld",&n,&k);

long long  ans=C(n+k+1,k+2);

ans=(2*ans)%m;

ans=(ans-n+m)%m;

cout<<ans<<endl;

}

}