P2265 Roadside Ditch

There is a huge ditch network in a certain city, which can be approximated as an $n \times m$ rectangular grid. A sluice gate is installed at every grid point. We call any path from the sluice gate at the bottom-right corner of the network to the sluice gate at the top-left corner a “water flow.”

Given the length and width of the ditch network, find the number of water flows that only move left and up.

The input consists of $1$ line containing two integers $n$ and $m$.

Output a single integer $ans$, the number of water flows. Since the answer can be large, output the result modulo $1000000007$.

For $30\%$ of the testdata, $1 \leq m, n \leq 10$. For $50\%$ of the testdata, $1 \leq m, n \leq 1{,}000$. For $80\%$ of the testdata, $1 \leq m, n \leq 50{,}000$. For $100\%$ of the testdata, $1 \leq m, n \leq 1{,}000{,}000$. Translated by ChatGPT 5