# Matrix Sum, factorial(K) times

Given an N x M matrix. The task is to repeat the following steps K! times.

1. Add all the elements of the matrix and get a matrix sum (S) % mod 10^9 + 7
2. Add S to all the elements. % mod 10^9 + 7
3. Repeat.

What I can think of regarding the complexity it will O(K! x N x M).

But K ranges from 1 to 10^5 and this is a huge number of iterations for a computer to process.

Is there a way to optimize these operations so that these can be performed using less computational resources.

Thank You.

• Do you use any matrix operations or simply have array that stores numbers and happen to be matrix? If this is from some contest please credit the sources. What have you tried so far? – Evil Jul 17 '17 at 3:56
• What's the source where you encountered this problem? Can you credit the original source? – D.W. Jul 17 '17 at 6:25

Suppose that the original elements are $a_{ij}^{(1)}$. Their sum is $S^{(1)} = \sum_{ij} a_{ij}^{(1)}$, and the new elements are $a_{ij}^{(2)} = a_{ij}^{(1)} + S^{(1)}$. The new sum is $S^{(2)} = \sum_{ij} a_{ij}^{(1)} + nmS^{(1)} = (1+nm)S^{(1)}$, and the new elements are $a_{ij}^{(3)} = a_{ij}^{(1)} + (2+nm)S^{(1)}$. The new sum is $S^{(3)} = S^{(1)} + nm(2+nm)S^{(1)} = (1+nm)^2S^{(1)}$, and so on.
More generally, you can prove by induction that $S^{(t)} = (1+nm)^{t-1} S^{(1)}$ and $a_{ij}^{(t)} = a_{ij}^{(1)} + \frac{(1+nm)^{t-1}-1}{nm} S^{(1)}$. It remains to find a fast way to calculate expressions such as $S^{(k!)} = (1+nm)^{k!-1} S^{(1)}$ modulo the given prime $p = 10^9 + 7$. You do the rest.