Range Set

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).

Examples

Input

4 2 3

Output

11

Input

10 7 2

Output

533

Input

1000 100 10

Output

828178524

inputFormat

input are integers.

Input

Input is given from Standard Input in the following format:

N A B

outputFormat

Output

Print the number of different strings that x can be after Snuke finishes doing operations, modulo (10^9+7).

Examples

Input

4 2 3

Output

11

Input

10 7 2

Output

533

Input

1000 100 10

Output

828178524

样例

4 2 3

11