Числа Фибоначчи. Объяснить код

Дано: Для решения задачи считываем два целых числа i и j такие, что 1 ≤ i, j ≤ 10^6.

Найти: Нужно вывести остаток от деления НОД чисел Fi и Fj на 10^9.

Решение: По свойству из Википедии: «Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов», получаем, что НОД(F_n,F_m) = F_{НОД(n,m)}.

Значит, нам нужно найти НОД для чисел i и j из условия, после чего найти соответствующее число Фибоначчи по модулю 1000000000.

Код от Harry:

#include <fstream>
using namespace std;
int nod(int a, int b) // Алгоритм Евклида
{
    while (a && b) if (a > b) a %= b; else b %= a;
    return a + b;
}
int main()
{
    int i, j; // вводимые числа
    ifstream fin;
    fin.open("INPUT.TXT");
    fin >> i >> j; // считываем i и j
    fin.close();
    int F0 = 0, F1 = 1; // по условию
    for (i = nod(i, j); i > 0; --i)  // ищем нужное число..
    {
        int F = (F0 + F1) % 1000000000;// .. по модулю 1000000000
        F0 = F1;
        F1 = F;
    }
    ofstream fout;
    fout.open("OUTPUT.TXT");
    fout << F0; //остаток от деления НОД чисел Fi и Fj на 10^9
    fout.close();
    return 0;
}

Я не очень понимаю фразу: "после чего найти соответствующее число Фибоначчи по модулю 1000000000". Может ли кто-то объяснить ее и соответствующую часть кода подробнее? Т.е. вот эту:

for (i = nod(i, j); i > 0; --i)  // ищем нужное число..
{
    int F = (F0 + F1) % 1000000000;// .. по модулю 1000000000
    F0 = F1;
    F1 = F;
}

Заранее спасибо!