Друзі Зеника
Обмеження: 2 сек., 256 МіБ
У Зеника є \(m\) друзів, яких він дуже поважає. Він вирішив купити деяку кількість яблук і розділити їх між собою і друзями. Зеник знає, що для того аби друзі і його поважали, він має дати кожному з них якомога більшу кількість яблук. Крім того, усі друзі повинні отримати однакову кількість яблук. Ті яблука, які залишаться, він забере собі. Іншими словами, якщо в Зеника є \(x\) яблук, то він віддасть кожному другові по \(x\) div \(m\) яблук, а собі візьме решту — \(x\) mod \(m\) яблук.
Зараз Зенику потрібно вирішити, скільки яблук йому купити початково. Він вирішив, що кількість яблук, яку він отримає, має бути в проміжку \([a, b]\) (границі включно). Окрім цього, у нього недостатньо грошей, щоб купити більше ніж \(n\) яблук. (Зауважте, що він може купити 0 яблук.)
Допоможіть Зенику порахувати кількість варіантів покупки, які б задовольняли його вимоги.
Вхідні дані
У єдиному рядку задано чотири цілих числа \(n\), \(m\), \(a\) та \(b\) — максимальну кількість яблук, яку може купити Зеник, кількість друзів, найменшу та найбільшу кількість яблук, яку може отримати Зеник.
Вихідні дані
У єдиному рядку виведіть одне ціле число — відповідь на задачу.
Обмеження
\(1 \le n, m \le 10^9\),
\(0 \le a \le b \le 10^9\).
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 7 4 1 5 | 6 |
| Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
|---|