C. Ойн баяр

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Италийн алдарт Математикч Леонард Фибоначчийн $900$ насны ой болоход $60$ хүрэхгүй жил үлджээ. Ийм том баяр мэдээж том хэмжээний бэлтгэл ажил шаардана.

Дима уг тэмдэглэлт өдөрт зориулж дараах бодлогыг бодохоор болсон. Танд $l, l+1, l+2, ... , r$ индекс байгаа бөгөөд та дээрх индекстэй фибоначчийн тоонуудаас яг $k$-г сонгож авсан дэд олонлоуудыг авч үзье. Ингээд уг олонлогын бүх элементийнх нь хамгийн их ерөнхий хуваагч-г (ХИЕХ) олно. Дима бүх олдсон ХИЕХ дундаас хамгийн ихийг нь олохыг хүсч байгаа юм.

Танд сануулахад Фибоначчийн тоо нь $F_1 = 1$, $F_2 = 1$, $n ≥ 3$ үед $F_n = F_{n-1}+F_{n-2}$ байдаг.

Димад уг бодлогыг бодох хагас зуун жил байна. Харин танд ердөө хоёр цаг л байх шив. Хариу маш том байж болох тул түүнийг $m$-д хуваасан үлдэгдлийг хэвлэнэ үү.

Оролт

Нэг мөрөнд $m$, $l$, $r$,$k$ ($1 ≤ m ≤ 10^9$; $1 ≤ l < r ≤ 10^{12}$; $2 ≤ k ≤ r - l + 1$) тоонууд өгөгдөнө.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Гаралт

Бодлогын хариу болох тоог $m$-д хуваасны үлдэгдлийг хэвлэ.

Орчуулсан: zoloogg

Жишээ тэстүүд

Оролт
10 1 8 2
Гаралт
3
Оролт
10 1 8 3
Гаралт
1
Сэтгэгдлүүдийг ачааллаж байна...