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

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

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

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