Всем привет, год назад в одном олимпиаде приходило одна задача, найки K-ое число фибоначчи по модулью 1е9+7 где -1e18 <= k <= 1e18

Если бы K было бы 0 <= K <= 1e18 то такое можно было решать за log(K) но тута K может быть отрицательным и я не знаю что делать

Можете помочь как решить эту задачу?