I use this formula: f(N)+f(n-2) where F(0)=1, F(1)=1, F(N)=F(N-1)+F(N-2). But wa. What is in the test 4. I checked the answer for N=7000 at the forum and it matches the answer that my program gives. Can anybody give me a test for 4.

We can state that f(21)=4181*f(1)+6765*f(2), f(22)=6765*f(1)+10946*f(2). Wherefore we can calculate f(i),f(i+1) with N/20 operations. All we need is addition of two long numbers (I used base 10000 for them) and  multiplication of long number and simple one, that's all. The usage of recursion formula f(2n)=f^2(n)+f^(n+1) (or something like that) is overridden here by the cost of multiplication of two long numbers.

@Spirit:
If you want to I can give you my accepted Java source, please give me your mail, but I'm interested in any accepted C++ solutions, please send to tabledott@gmail.com, cause all my C++ efforts were unsucessful, btw I used base 10^9 and I was    losing accuracy :)

I'll send you my C++ solution.
I made it in O(n) with only + in long arithmetics, but it's well optimized.

If anybode else is interested in my solution mail to me alutsenko[at]bk[dot]ru