← 返回题目列表

Codeforces · 226/C

C. 周年纪念日

中文机器翻译题面 查看原题

距离意大利著名数学家列奥纳多·斐波那契诞辰 900 周年还有不到 60 年的时间。当然,如此重要的周年纪念日需要做很多准备。

Dima 确信,在大日子之前学会解决以下问题将会很棒:给你一个集合 A,由数字 l、l + 1、l + 2、...、r 组成;让我们考虑它的所有 k 元素子集;对于每个这样的子集,让我们找到具有索引的斐波那契数的最大公约数,该索引由子集元素确定。在所有找到的公约数中,迪马对最大的一个感兴趣。

Dima 要求提醒您,斐波那契数是数字序列的元素,其中 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 所得的余数。

示例

输入 #1

10 1 8 2

输出 #1

3

输入 #2

10 1 8 3

输出 #2

1