K-angulation#3665

K-angulation

1 second
256 megabytes
Very hard

A (k_1, k_2)-angulation of a convex -gon is defined as a way to divide it into smaller polygons using diagonals that do not intersect each other, except at their endpoints. Each resulting polygon must have at least k_1 vertices and at most k_2 vertices.

Your task is to determine the number of distinct (k_1, k_2)-angulations of a convex -gon. Two angulations are considered different if there is at least one diagonal present in one angulation that is not present in the other.

Input

The input consists of a single line containing three natural numbers: , k_1, and k_2 (3 \leq N \leq 500, 3 \leq k_1 \leq k_2 \leq N).

Output

Output the number of (k_1, k_2)-angulations modulo 10^9+7.

Examples

Example 1

Loading
Loading