My algorithm for calculating the modulo of a very large fibonacci number is too slow

there is no need to use BigInteger because:

1*2*3*4*...*N mod M
1+2+3+4+...+N mod M

is the same as

(...(((1*2 mod M)*3 mod M)*4 mod M)...*N mod M)
(...(((1+2 mod M)+3 mod M)+4 mod M)...+N mod M)

that should speed up a lot ... from (assumed karatsuba multiplication) O(3*N*(n^log2(3))) and or addition O(N*n) into linear O(N) where n is proportional bitwidth of your multiplicants/additionals with also far better constant time ...

IIRC there where also formulas for fast fibonaci computation (converting O(N) into something near O(log(N))

Here few examples: fast fibonacci algorithms

Here C++ example of naive (modfib0) and fast (modfib1 using power by squaring of 2x2 matrix) algo:

//---------------------------------------------------------------------------
int modfib0(int n,int m)
    {
    for (int i=0,x0=0,x1=1;;)
        {
        if (i>=n) return x1; x0+=x1; x0%=m; i++;
        if (i>=n) return x0; x1+=x0; x1%=m; i++;
        }
    }
//---------------------------------------------------------------------------
// matrix 2x2:  0 1
//              2 3
void modmul2x2(int *c,int *a,int *b,int m)  // c[4] = a[4]*b[4] %m
    {
    int t[4];
    t[0]=((a[0]*b[0])+(a[1]*b[2]))%m;
    t[1]=((a[0]*b[1])+(a[1]*b[3]))%m;
    t[2]=t[1]; // result is symetric so no need to compute: t[2]=((a[2]*b[0])+(a[3]*b[2]))%m;
    t[3]=((a[2]*b[1])+(a[3]*b[3]))%m;
    c[0]=t[0];
    c[1]=t[1];
    c[2]=t[2];
    c[3]=t[3];
    }
void modpow2x2(int *c,int *a,int n,int m)   // c[4] = a[4]^n %m
    {
    int t[4];
    t[0]=a[0]; c[0]=1;
    t[1]=a[1]; c[1]=0;
    t[2]=a[2]; c[2]=0;
    t[3]=a[3]; c[3]=1;
    for (;;)
        {
        if (int(n&1)!=0) modmul2x2(c,c,t,m);
        n>>=1; if (!n) break;
        modmul2x2(t,t,t,m);
        }
    }
int modfib1(int n,int m)
    {
    if (n<=0) return 0;
    int a[4]={1,1,1,0};
    modpow2x2(a,a,n,m);
    return a[0];
    }
//---------------------------------------------------------------------------

beware in order to comply with your constraints the used int variable must be at least 64bit wide !!! I am in old 32 bit environment and did not want to spoil the code with bigint class so I tested only with this:

int x,m=30000,n=0x7FFFFFFF;
x=modfib0(n,m);
x=modfib1(n,m);

And here results:

[10725.614 ms] modfib0:17301 O(N)
[    0.002 ms] modfib1:17301 O(log2(N))

As you can see the fast algo is much much faster than linear one ... however the measured time is too small for Windows environment and most of its time is most likely overhead instead of the function itself so I think it should be fast enough even for n=10^18 as its complexity is O(log2(N)) I estimate:

64-31 = 33 bits
0.002 ms * 33 = 0.066 ms

so the 64 bit computation should be done well below 0.1 ms of execution time on my machine (AMD A8-5500 3.2 GHz) which I think is acceptable...

The linear algo for 64bit would be like this:

10.725614 s * 2^33 = 865226435999039488 s = 27.417*10^9 years

but as you can see you would dye of old age long before that ...