题目描述

设 $F$ 是斐波那契数列，在 $[l,r]$ 中选 $k$ 个数 $a_1...a_k$，使得 $\gcd(F_{a_1},F_{a_2},...,F_{a_k})$ 尽可能大。输出对 $m$ 取模后的结果。

输入格式

一行四个整数 $m,l,r,k$，$1\le m\le 10^9$，$1\le l<r\le 10^{12}$，$2\le k\le r-l+1$。

输出格式

输出一个整数表示答案。

10 1 8 2

3

10 1 8 3

1