Flowers

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

This package preserves the original task mechanism. Có hai loại khối: khối đỏ dài $1$ và khối trắng dài $k$. Một dải dài $x$ được ghép từ các khối này. Hãy tính tổng số cách cho mọi độ dài từ $a$ đến $b$.

Input

Dòng duy nhất chứa $k,a,b$ trong phiên bản một truy vấn của PHOJ.

Output

In tổng số cách modulo $10^9+7$.

Subtasks

• Subtask 1 — 20 points: small data.
• Subtask 2 — 30 points: medium data.
• Subtask 3 — 50 points: full PHOJ package limits.

Examples

Input

2 3 3

Output

3

Explanation

The output follows directly from the rules above.