You are playing a game with your friend. There is a pile with ~N~ stones and a chosen number ~K~. You and your friend alternate turns to remove some number of stones. Call ~s_i~ the number of stones removed on the ~i^\text{th}~ turn. ~s_1=1~, that is, the first player must remove exactly ~1~ stone. After that, on the ~i^\text{th}~ turn, the current player is allowed to remove any number of stones between ~1~ and ~s_{i-1}+K~. The player who removes the last stone wins. Given that you are the first player, for how many possible ~N~ between ~X~ and ~Y~ inclusive can you guarantee a win?

Constraints

For all subtasks:

~1 \le K \le 10^{15}~

Subtask 1 [10%]

~1 \le X, Y \le 100~

Subtask 2 [10%]

~1 \le X, Y \le 5\,000~

Subtask 3 [40%]

~1 \le X, Y \le 1\,000\,000~

Subtask 4 [40%]

~1 \le X, Y \le 10^{15}~

Input Specification

The first line will have three space-separated integers, ~K~, ~X~, and ~Y~ in that order.

Output Specification

Output the answer.

Sample Input

5 11 41

Sample Output

6