in the RECURSIVE SEQ 1 implementation , we have taken modulus earlier and not at the final step
C[i][j] = (C[i][j] + (A[i][x]*B[x][j])%MOD)%MOD;
so will it not change my ans;
and can we make the 2d matrix as
vector<vector>T instead the one made in the ques which is vector<vector>T(k+1,vector(k+1));
Since, (AB)%C = ((A%C)(B%C))%C, it won’t affect the final answer. We’re doing it to prevent overflow of number. Suppose A=10^6, B=10^6 and you have to find (A^4 * B^4)%1000, then you simply do ((A%1000)*(B%1000))%1000 four times so that the final value doesn’t cross the integer limit.
For declaring a 2D vector, always use the std::vector::vector(count, value) constructor that accepts an initial size and a default value.