This problem is almost identical to Bertrand's Ballot Problem, and is solved in a similar way.

The answer to the problem is given by the formula ~\frac{N - KM}{N + M} {N + M \choose K}~, where ~N~ represents the votes that André received, ~M~ represents the votes that Bertrand received and ~K~ is the minimum difference between their votes. Note that ~{N \choose K} = \frac{N\,!}{(N - K)\,!K\,!}~ is the choose function. Here is a detailed proof of the formula.

To calculate the answer~\bmod 10^9 + 7~, use the property ~(A \times B) \bmod M \equiv ((A \bmod M) \times (B \bmod M)) \bmod M~ when calculating the choose function.

For the division, use the property ~(A \div B) \bmod M \equiv ((A \bmod M) \times (B^{-1} \bmod M)) \bmod M~, where ~B^{-1}~ is the modular inverse of ~B \bmod M~.

Time Complexity: ~\mathcal{O}(\min(N, M))~, due to the fact that the complexity of the choose function ~N \choose K~ is ~\mathcal{O}(\min(K, N - K))~