Really enjoyed this kata. Very interesting and fun to code

You can do more research :) If you read the description of the kata carefully, you can find a link with some hints. Going through the linked document, you can find a very convoluted hint on some algorithm for calculating Fibonacci numbers more efficiently than in linear fashion. Hint is very complex for a person not very familiar with math (I could not get jack from it), but it's at least some starting point for further research.

I haven't tried your solution, but you can verify it by running your solution for values like n=1_000_000 and n=1_500_000.
However, even if you manage to get it in performant way, I would be concerned with accuracy issues. Every exponentiation operation loses precision significantly, and with exponents of such magnitude, I think you won't manage to get accurate result. I did not check it by myself though, so I might be wrong :)

You may also want to read docs on block code formatting: https://github.com/codewars/codewars.com/wiki/Markdown-Formatting#block-code-formatting