/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
すぬけくんは長さ N の文字列 x を持っています．
最初，x のすべての文字は 0 です．
すぬけくんは，以下の 2 種類の操作を好きな順序で好きな回数行うことができます．
- x の連続する A 文字を選んで，それらをすべて
0にする． - x の連続する B 文字を選んで，それらをすべて
1にする．
すぬけくんが操作を終えたあとの x としてありうるものが何通りあるかを求めてください． ただし答えは非常に大きくなることがあるので．10^9+7 で割ったあまりを求めてください．
制約
- 1 \leq N \leq 5000
- 1 \leq A,B \leq N
- 入力される値はすべて整数である．
入力
入力は以下の形式で標準入力から与えられる．
N A B
出力
すぬけくんが操作を終えたあとの x としてありうるものが何通りあるかを 10^9+7 で割ったあまりを出力せよ．
入力例 1
4 2 3
出力例 1
11
例えば，x=0011,1111 などはありえますが，x=0110 はありえません．
入力例 2
10 7 2
出力例 2
533
入力例 3
1000 100 10
出力例 3
828178524
Score : 800 points
Problem Statement
Snuke has a string x of length N.
Initially, every character in x is 0.
Snuke can do the following two operations any number of times in any order:
- Choose A consecutive characters in x and replace each of them with
0. - Choose B consecutive characters in x and replace each of them with
1.
Find the number of different strings that x can be after Snuke finishes doing operations. This count can be enormous, so compute it modulo (10^9+7).
Constraints
- 1 \leq N \leq 5000
- 1 \leq A,B \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A B
Output
Print the number of different strings that x can be after Snuke finishes doing operations, modulo (10^9+7).
Sample Input 1
4 2 3
Sample Output 1
11
For example, x can be 0011 or 1111 in the end, but cannot be 0110.
Sample Input 2
10 7 2
Sample Output 2
533
Sample Input 3
1000 100 10
Sample Output 3
828178524