Description

Input & Output

Sample Input

1

2 3 100 6

Sample Output

1

82

Constraint

对于100%的数据，0 ≤ n ≤ 10^9 ，1 ≤ M ≤ 10^9 ，1 ≤ F_0 ≤ F_1 ≤ 10^6

Solution