Ước chung Fibonacci

Dãy Fibonacci được định nghĩa bởi $F_1=1$, $F_2=1$ và $F_n=F_{n-1}+F_{n-2}$ với mọi $n\ge 3$.

Cho tập $A=\{l,l+1,l+2,\dots ,r\}$. Xét mọi tập con gồm đúng $k$ phần tử của $A$. Với mỗi tập con $\{a_1,a_2,\dots ,a_k\}$, ta tính ước chung lớn nhất của các số Fibonacci mang chỉ số tương ứng:

$$g=gcd(F_{a_1},F_{a_2},\dots ,F_{a_k}).$$

Trong tất cả các giá trị $g$ thu được, gọi $G$ là giá trị lớn nhất. Hãy in ra phần dư của $G$ khi chia cho $m$.

Lưu ý thứ tự của hai phép toán: phải lấy giá trị lớn nhất trên các ước chung rồi mới chia lấy dư cho $m$, chứ không phải lấy giá trị lớn nhất của các phần dư.

Dữ liệu vào

Một dòng duy nhất chứa bốn số nguyên $m$, $l$, $r$, $k$ cách nhau bởi dấu cách.

Dữ liệu ra

Một số nguyên duy nhất là phần dư của $G$ khi chia cho $m$.

Ràng buộc

• $1\le m\le {10}^9$
• $1\le l<r\le {10}^{12}$
• $2\le k\le r-l+1$

Ví dụ