Вывести остаток от деления НОД чисел F(i) и F(j) на 10^9. (F - Число Фибоначчи)

#include <bits/stdc++.h>
 
using namespace std;
 
 
unsigned __int64 Fib(unsigned __int64 f) //Здесь считаю число Фибоначчи чисел i,j.
{
unsigned __int64 f1,f2,ff=0,i=0;           // unsigned __int64 - я использую этот тип чтобы гарантированно "помещался" в переменных из за этих ограничениий
f1=0;
f2=1;
while(i<f){
    ff=(f2+f1)%1000000000;
    f2=f1;
    f1=ff;
    i++;
}
return ff;
}
 
int main()
{
    ifstream fin("c:\input.txt");
    ofstream fout("c:\output.txt");
    unsigned __int64 a,b,i,j,NOD;
    fin>>i>>j;
    i=Fib(i);
    j=Fib(j);
 
    a=i;
    b=j;
    while(a*b>0){      //Здесь я считаю НОД чисел F(i),F(j).
        if(a>=b)a=a%b;
        else b=b%a;
    }
    NOD=a+b;
    fout<<NOD%1000000000; //потом вывожу остаток от деления НОД-а на 10^9.
}

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ifstream fin("c:\input.txt");
    ofstream fout("c:\output.txt");
    unsigned long long NOD,i,j,f1 = -1,f2 = 1,f = 0,k;
    long long MOD = 1000000000;
    fin>>i>>j;
 
    while(i*j>0){
        if(i>j)i=i%j;
        else j=j%i;
    }
    NOD=i+j;
 
    for(k=0;k<=NOD;k++)
    {
        f=(f2+f1)%MOD;
        f1=f2;
        f2=f;
    }
    fout<<f%MOD;
}