There is a problem that I solved earlier: Find how many permutations p s.t. $$$|p_i-i|\leq k$$$ for all $$$i$$$. Constraints: $$$n\leq 10^9,k\leq 4$$$. I solved it using matrix multiplication (converted ARC132C 's transitions to matrix form), but naively multiplying the matrix creates the insane complexity of $$$O(64^k*\log(n))$$$. By skipping the non-zero terms in the left hand side, I was able to get it passed. Can anyone explain why this passes, and maybe prove the complexity of it?