Today I solved this problem using some nice (and easy to find) formulas for computing F[n]:
F[2n] = F[n]*(F[n-1] + F[n+1]) and
F[2n-1] = F^2[n-1] + F^2[n]
with these you cand recursevly compute F[n] fast enough (~0.25 sec). I also precalculated a table with first 2000 Fibonacci and when the recursion dropped below 2000 it returned the computed value.
I see some nice times on the best AC list. Will you please tell us how you did it? What formulas, optimizations...
Thank you

Where can I find fast(n*log(n))long multiplication in acceptable form?

From what index do you start? F(0)=1 and F(1)=1 or not?
Cause I have such formulas:
F(2n+1)=F(N)*(F(n-1)+F(n+1));
F(2n)=F^2(N)+F^(N-1)