#GYM104603E. Finding progressions

Finding progressions

Description

Catalina needs help with her Math homework, which consists of finding all the increasing arithmetic progressions of integers (*) that meet the following conditions:

  • The progression contains the number $A$
  • The sum of the terms of the progression is $S$
  • All terms of the progression are in the range $[L, R]$

Catalina is a responsible girl and doesn't want someone else to solve the task for her, but she could use a little help. What Catalina needs is for you to tell her how many progressions exist under these conditions, so that she could know when to stop searching.

(*) An increasing arithmetic progression of integers is a non-empty list of $n$ integer numbers $x_1, x_2, \ldots , x_n$ where $x_i - x_{i-1} = D > 0$ for every integer $i$ such that $2 \leq i \leq n$, where $D$ is a positive integer. For example, $[7]$, $[1, 2, 3]$ and $[2, 4, 6, 8]$ are valid progressions, but $[5, 1]$, $[2, 4, 8]$ and $[3, 6, 9, 6]$ are not.

A single line with four integers $A$, $S$, $L$ and $R$ ($1 \leq L \leq A \leq R \leq 10^{12}$, $1 \leq S \leq 10^{18}$, $0 \leq R-L \leq 10^5$).

A single line with an integer indicating how many progressions meet the conditions described by the statement.

Input

A single line with four integers $A$, $S$, $L$ and $R$ ($1 \leq L \leq A \leq R \leq 10^{12}$, $1 \leq S \leq 10^{18}$, $0 \leq R-L \leq 10^5$).

Output

A single line with an integer indicating how many progressions meet the conditions described by the statement.

5 15 1 10
5 15 2 10
7 30 3 26
5 5 5 5
6
4
4
1

Note

The 6 valid progressions for the first example are: $[5, 10]$, $[1, 5, 9]$, $[2, 5, 8]$, $[3, 5, 7]$, $[4, 5, 6]$ and $[1, 2, 3, 4, 5]$