Меньше 60 лет осталось до того, как исполнится 900 лет со дня рождения известного итальянского математика Леонардо Фибоначчи. Безусловно, к такому важному юбилею надо заранее основательно подготовиться.
Дима убежден, что неплохо было бы к знаменательной дате научиться решать следующую задачу: дано множество A, состоящее из чисел l, l + 1, l + 2, ..., r; рассмотрим все его k-элементные подмножества; для каждого такого подмножества найдем наибольший общий делитель чисел Фибоначчи с порядковыми номерами, заданными элементами подмножества. Среди всех найденных наибольших общих делителей Диму интересует самый большой.
Дима просил напомнить, что числа Фибоначчи — элементы числовой последовательности, в которой F1 = 1, F2 = 1, Fn = Fn - 1 + Fn - 2 для n ≥ 3.
У Димы впереди еще больше полувека, чтобы решить поставленную задачу, а у Вас всего два часа. Посчитайте остаток от деления искомого наибольшего общего делителя на m.