c++ - Fibonacci, but with different starting numbers. Code works in most cases, but not all

Question

So I have an exercise of finding a Fibonacci sequence but with different starting number and I can't figure out why my code works most of the time, but not in some cases.

My code is based on a formula (link: https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/)

If n is even then k = n/2:
F(n) = [2*F(k-1) + F(k)]*F(k)

If n is odd then k = (n + 1)/2
F(n) = F(k)*F(k) + F(k-1)*F(k-1)

-

#include <map>
#include <iostream>
#include <cmath>
using namespace std;

#define long long long
map<long, long> F;

long f(long n, long M) {
    if (F.count(n)) return F[n];
    long k = n / 2;
    if (n % 2 == 0) { // n=2*k
        return F[n] = (f(k, M)*f(k, M) + f(k - 1, M)*f(k - 1, M)) % M;
    }
    else { // n=2*k+1
        return F[n] = (f(k, M)*f(k + 1, M) + f(k - 1, M)*f(k, M)) % M;
    }
}

int main() {
        long a, b, M, n;
        cin >> a >> b >> n >> M;
        M = pow(10, M); //modulo
        F[0] = b;
        F[1] = a + b;
        //base cases
        for (int i = 2; i < 100; i++) F[i] = (F[i - 1] + F[i - 2]) % M;


        if (n != 0) cout << f(n - 1, M) << endl;
        else cout << a<<endl;

        F.clear();


}

a - is the first number of the sequence. b - the second. n - which number of the sequence i want to find. m - modulo.

I don't understand why it works with cases like

98 25 1000000000 1              //answer is 3

but it doesn't work with

34 88 224242 2     //my answer is 12, correct is 92

code works fine with regular Fibonacci starting numbers (0 and 1)

I would be really grateful for your help.

Thank you.

Answer 1

Waitting for answers