← 返回题目列表

AtCoder · abc034_c

C. 路线

中文机器翻译题面 查看原题

問題文

横 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