Giải bài trực tuyến

Cho 1 số nguyên dương K và dãy số F gồm n phần tử được tạo như sau:

• F[1] = 1;
• F[2] = 2;
• F[i] = (F[i - 1] + F[i - 2]) mod K; (3 ≤ i ≤ n)

Yêu cầu: Hãy cho biết giá trị thứ S của dãy F khi sắp xếp không giảm.

Dữ liệu vào

Gồm 1 dòng duy nhất chứa 3 số n, k , s.

Dữ liệu ra

1 số duy nhất là kết quả tương ứng.

Giới hạn

• 1 ≤ s ≤ n ≤ 10¹⁸
• 1 ≤ k ≤ 10⁴

Ví dụ

Dữ liệu vào
5 2 4

Dữ liệu ra
1