Under construction

Still being built. Things may change

Walking Home Separately

Time limit1sMemory limit1024 MB

Summary
Count the ways two people can walk from (1,1) to (N,M) using only right and down moves, without sharing any cell except the start and the end.
Level

Medium7 of 10

Topics
Combinatorics, Math
Solved
No attempts yet

Problem

Tosuni and Tojuni had a big fight and now want to walk home separately.

Rabbit couple arguing

Tosuni and Tojuni move on a two-dimensional grid of NN rows and MM columns, and they can only move right or down.

Let (i,j)(i, j) be the position reached from (1,1)(1, 1) by moving down i−1i-1 cells and right j−1j-1 cells.

The couple starts at (1,1)(1, 1) and moves one cell at a time at the same moment until they reach their home at (N,M)(N, M).

During this walk, they want to avoid meeting in the same cell, except at the starting point and at the destination (home).

Rabbit couple walking home

Find the number of ways the couple can walk home.

Input

The first line contains integers NN and MM separated by a space. (2≤N,M≤200,0002 \le N, M \le 200\\,000)

Output

Print the number of ways the couple can walk home, modulo 109+710^9+7. (109+710^9+7 is a prime number.)

Examples3

  1. Example 1

    Input
    2 2
    
    Expected output
    2
    
  2. Example 2

    Input
    3 4
    
    Expected output
    12
    
  3. Example 3

    Input
    123456 78901
    
    Expected output
    620455136