分数: 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