Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

C. Юбилей
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Меньше 60 лет осталось до того, как исполнится 900 лет со дня рождения известного итальянского математика Леонардо Фибоначчи. Безусловно, к такому важному юбилею надо заранее основательно подготовиться.

Дима убежден, что неплохо было бы к знаменательной дате научиться решать следующую задачу: дано множество A, состоящее из чисел l, l + 1, l + 2, ..., r; рассмотрим все его k-элементные подмножества; для каждого такого подмножества найдем наибольший общий делитель чисел Фибоначчи с порядковыми номерами, заданными элементами подмножества. Среди всех найденных наибольших общих делителей Диму интересует самый большой.

Дима просил напомнить, что числа Фибоначчи — элементы числовой последовательности, в которой F1 = 1, F2 = 1, Fn = Fn - 1 + Fn - 2 для n ≥ 3.

У Димы впереди еще больше полувека, чтобы решить поставленную задачу, а у Вас всего два часа. Посчитайте остаток от деления искомого наибольшего общего делителя на m.

Входные данные

В первой строке записаны четыре целых числа через пробел m, l, r и k (1 ≤ m ≤ 109; 1 ≤ l < r ≤ 1012; 2 ≤ k ≤ r - l + 1).

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Выходные данные

Выведите единственное целое число — остаток от деления искомого наибольшего общего делителя на m.

Примеры
Входные данные
10 1 8 2
Выходные данные
3
Входные данные
10 1 8 3
Выходные данные
1