C - Range Set /

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