問題文
横 W x 垂直 我有一个 H 网格。从左边开始 从底部数第 i 在第 j 个方格中, 它的编号为 (i, j) 。高桥君是方形的 您可以继续 (i, j) 减去 (i+1, j) 或 至少 (i, j+1) 。高桥君 到 (1, 1) 减去 (W, H) 的路线数量为 除以 1,000,000,007 后求余数。
入力
输入是按以下格式从标准输入给出的。
W H
- 2 ≤ W, H ≤ 10^5 已满足。
部分点
针对此问题设置了部分分数。满分是101分。 如果您对满足- W, H ≤ 10 的数据集回答正确,您将获得 50 分。 如果您对满足
- W, H ≤ 1000 的数据集回答正确,除了上述分数外,您还将获得 50 分。 打印除以
出力
高桥君 当您移动到 (1, 1) 减去 (W, H) 的路线数量为 除以 1,000,000,007 后的余数。 在输出末尾添加换行符。 有 10 条路线:
入力例1
4 3
出力例1
10
- (1, 1) → (1, 2) → (1, 3) → (2, 3) → (3, 3) → (4, 3)
- (1, 1) → (1, 2) → (2, 2) → (2, 3) → (3, 3) → (4, 3)
- (1, 1) → (1, 2) → (2, 2) → (3, 2) → (3, 3) → (4, 3)
- (1, 1) → (1, 2) → (2, 2) → (3, 2) → (4, 2) → (4, 3)
- (1, 1) → (2, 1) → (2, 2) → (2, 3) → (3, 3) → (4, 3)
- (1, 1) → (2, 1) → (2, 2) → (3, 2) → (3, 3) → (4, 3)
- (1, 1) → (2, 1) → (2, 2) → (3, 2) → (4, 2) → (4, 3)
- (1, 1) → (2, 1) → (3, 1) → (3, 2) → (3, 3) → (4, 3)
- (1, 1) → (2, 1) → (3, 1) → (3, 2) → (4, 2) → (4, 3)
- (1, 1) → (2, 1) → (3, 1) → (4, 1) → (4, 2) → (4, 3)
入力例2
123 456
出力例2
210368064