• + 2 comments

    Just for fun, a code golf solution in Python:

    def solve(n, m):
        inv=lambda a,b,c,d:(b<2)*d or inv(b,a%b,d,c-a//b*d)
        p,q,C=1,1,10**9+7
        for i in range(m,n+m-1):
            p,q=p*i%C,q*(i-m+1)%C
        return p*inv(q,C,1,0)%C
    

    To avoid timing out this uses the factorial formula for the choose function, modding out at each step so that multiplication does not become too costly. Note that building tables can take quadratic time while the formula takes linear time. To tackle the division in the formula inside the modulus, a modular inversion function based on the Euclidean algorithm is written on the first line.