You can multiply numbers with modulo less than 1012 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;
}