You can multiply numbers with modulo less than 10¹² using O(1) operations.

long long multiply(long long a,long long b,long long m)
{
    long long a1=a>>20;
    long long a2=a&1048575;
    long long b1=b>>20;
    long long b2=b&1048575;
    return (a2*b2 + ((a1*b2+a2*b1)<<20) + ((a1*b1<<20)%m<<20))%m;
}