<reponame>bristy/codemania<filename>HackerRank/algo/Codesprint5/matrixtracing.cpp
#include <iostream>
using namespace std;


// Use 64 bits integers to avoid overflow errors during multiplication.
long modPow(long a, long x, long p) {
    //calculates a^x mod p in logarithmic time.
    long res = 1;
    while(x > 0) {
        if( x % 2 != 0) {
            res = (res * a) % p;
        }
        a = (a * a) % p;
        x /= 2;
    }
    return res;
}

long modInverse(long a, long p) {
    //calculates the modular multiplicative of a mod m.
    //(assuming p is prime).
    return modPow(a, p-2, p);
}
long modBinomial(long n, long k, long p) {
// calculates C(n,k) mod p (assuming p is prime).

    long numerator = 1; // n * (n-1) * ... * (n-k+1)
    for (int i=0; i<k; i++) {
        numerator = (numerator * (n-i) ) % p;
    }

    long denominator = 1; // k!
    for (int i=1; i<=k; i++) {
        denominator = (denominator * i) % p;
    }

    // numerator / denominator mod p.
    return ( numerator* modInverse(denominator,p) ) % p;
}

int calculate(int tar, int choice) {
    return (int)( modBinomial(tar, choice, 1000000007) );
}
int main(){
    int t;
    int n, m;
    cin>>t;
    while(t--){
        cin>>n>>m;
        cout<<calculate(n+m-2, n-1)<<"\n";
    }

    return 0;
}
