Clear[f];
f[0] := 0;
f[1] := 1;
f[2] := 1;
f[n_ /; Mod[n, 3] == 0] := f[n] = With[{m = n/3},
    Mod[5 f[m]^3 + 3 (-1)^m f[m], 10^10]];
f[n_ /; Mod[n, 3] == 1] := f[n] = With[{m = (n - 1)/3},
    Mod[f[m + 1]^3 + 3 f[m + 1] f[m]^2 - f[m]^3, 10^10]];
f[n_ /; Mod[n, 3] == 2] := f[n] = With[{m = (n - 2)/3},
    Mod[f[m + 1]^3 + 3 f[m + 1]^2 f[m] + f[m]^3, 10^10]];

1560546875

f[0] = 0
f[1] = 1
f[2] = 1
f[3] = 2
f[7] = 13
f[8] = 21
f[23] = 28657
f[24] = 46368
f[69] = 9030460994
f[70] = 2490709135
f[209] = 3274930109
f[210] = 9082304280
f[627] = 3331634818
f[628] = 5364519011
f[1881] = 6891052706
f[1882] = 7684747991
f[5645] = 9674730645
f[5646] = 6983060328
f[16935] = 3041238690
f[16936] = 6494990027
f[50805] = 9095828930
f[50806] = 1802444783
f[152415] = 8092298210
f[152416] = 439009787
f[457247] = 3467735873
f[457248] = 3439061376
f[1371742] = 3463150271
f[1371743] = 8878860737
f[4115226] = 976213368
f[4115227] = 2499441093
f[12345679] = 9190666621
f[12345680] = 4288166885
f[37037037] = 2169005442
f[37037038] = 1145757919
f[111111111] = 7067038114
f[111111112] = 440574219
f[333333333] = 6434013378
f[333333334] = 4572218287
f[1000000000] = 1560546875