got it, it is 9 times more !!!
With any reasonable mod (10^9 + 7, 998244353, etc.) that won’t happen. But in any case, that’s why I don’t recommend templating it 
1 Like
@galencolin I mean if our summation is (MOD-1) *(MOD-1)+...\ (100 \ times) it overflows for sure if our check is only of O(n^2). Are we checking this O(n^3) times and using modulo O(n^2) times?
if (x >= mod * mod) {
x -= mod * mod;
}
Yes. That exact code would go inside the triple for-loop after modifying the resultant matrix, and there would be an external double for-loop (or not external) with a single mod operation for each resultant element.
1 Like