← 返回题目列表

AtCoder · agc045_c

C. 范围设置

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

分数: 800 点

问题陈述

Snuke 有一根绳子 x 长度 N。 最初,每个角色 x is 0.

Snuke 可以按任意顺序执行任意次数的以下两个操作:

  • 选择 A 中的连续字符 x 并将它们中的每一个替换为 0.
  • 选择 B 中的连续字符 x 并将它们中的每一个替换为 1.

找出不同字符串的数量 x 可以在 Snuke 完成操作后进行。 这个计数可能会很大,所以计算它的模 (10^9+7).

约束

  • 1 \leq N \leq 5000
  • 1 \leq A,B \leq N
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N A B

输出

打印不同字符串的数量 x 可以在 Snuke 完成运算后,取模 (10^9+7).


示例输入 1

4 2 3

示例输出 1

11

例如, x 可以 0011 or 1111 最后,但不能 0110.


示例输入 2

10 7 2

示例输出 2

533

示例输入 3

1000 100 10

示例输出 3

828178524