What is the error in the code that calculates the Pisano period?

Question

C++ / C#

Given: algorithmic problem. It is necessary to find the modulus from dividing the n-th Fibonacci number by m. The problem is solved by calculating the Pisano period and using it instead of the modulus of the original nth number (because n can be very large). I came up with what I thought was a nice and simple solution:

vector<unsigned long long> cache = {0, 1};
vector<unsigned long long> seq = {0, 1};

unsigned long long fib(int n) {
    if (n >= cache.size()) {
        cache.push_back(fib(n-1) + fib(n-2));
    }
    return cache[n];
}

int main() {
    unsigned long long n, m;
    cin >> n >> m;

    for (int i = 2;; ++i) {
        seq.push_back(fib(i) % m);
        if(seq[i] == 1 && seq[i-1] == 0) {
            seq.pop_back();
            seq.pop_back();
            break;
        }
    }

    cout << seq[n % seq.size()];
}

It can be optimized for memory if you do not store seq, but this is a trifle. The problem is that this solution only works for small numbers. So, with n=2015 and m=3, 1 is displayed - this is the correct answer. But on large sequences (n=239, m=100), garbage begins to turn out. I found a solution to this problem ( link ) - conceptually it is almost the same, except for the mentioned optimization. What could be wrong in my code?

Answer 1

When calculating cache, numbers are not taken modulo. This means that long longs are overflowed very quickly and garbage happens. After all, the cycle can start at very large numbers. You should always take modulo m when calculating.
And, an obvious optimization - since you have fib () called from indexes increasing in order, instead of a function, do it right awayseq.push_back((seq[i-2]+seq[i-1]) % m);