Последовательность Фибоначчи определяется следующим рекуррентным выражением:

F_n = F_n−1 + F_n−2, где F₁ = 1 и F₂ = 1.

Оказывается, что число F₅₄₁, состоящее из 113 цифр, является первым числом Фибоначчи, у которого последние девять цифр образуют пан-цифровое число с цифрами от 1 до 9 (оно содержит все цифры от 1 до 9, но не обязательно в порядке возрастания). А число F₂₇₄₉, состоящее из 575 цифр, является первым числом Фибоначчи, у которого первые девять цифр образуют пан-цифровое число с цифрами от 1 до 9.

Известно, что число F_k является первым числом Фибоначчи, у которого как первые, так и последние девять цифр образуют пан-цифровые числа. Найдите k.