E. Finding progressions
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

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 \gt 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.

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.

Examples
Input
5 15 1 10
Output
6
Input
5 15 2 10
Output
4
Input
7 30 3 26
Output
4
Input
5 5 5 5
Output
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]$$$