Background

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.”

Problem Description

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

Input Format

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

Output Format

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

3 5

56

Hint

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