Числа Фибоначчи. Не проходит 6 тест на acmp

Последовательностью Фибоначчи называется последовательность чисел F0 = 0, F1 = 1, … , Fk = Fk-1 + Fk-2 (k > 1). Требуется найти наибольший общий делитель двух чисел Фибоначчи.

Входные данные Во входном файле INPUT.TXT записаны два целых числа i и j (1 ≤ i, j ≤ 10^6).

Выходные данные В выходной файл OUTPUT.TXT выведите остаток от деления НОД чисел Fi и Fj на 10^9.

Вот мой код:

#include <fstream>
using namespace std;
long double nod(long double a, long double b)
{
    if (a == b) {
        return a;
    }
    if (a > b) {
        long double tmp = a;
        a = b;
        b = tmp;
    }
    return nod(a, b - a);
}
long double fib(int n)
{
    double a = 0.0;
    double b = 1.0;
    double temp = 0.0;
    for (int i = 0; i < n; i++)
    {
        temp = b;
        b += a;
        a = temp;
    }
    return a;
}
int main()
{
    int i, j; // вводимые числа
    ifstream fin;
    fin.open("INPUT.TXT");
    fin >> i >> j;
    fin.close();
    long double Fi = fib(i); // число Фибоначчи от i
    long double Fj = fib(j); // число Фибоначчи от j
    ofstream fout;
    fout.open("OUTPUT.TXT");
    fout << fmod(nod(Fi, Fj), 1000000000); //остаток от деления НОД чисел Fi и Fj на 10^9
    fout.close();
    return 0;
}