This content is archived!

For the 2018-2019 school year, we have switched to using the WLMOJ judge for all MCPT related content. This is an archive of our old website and will not be updated.

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))


Read the problem.