<p>Given a <strong>0-indexed</strong> 2D integer matrix <code><font face="monospace">grid</font></code><font face="monospace"> </font>of size <code>n * m</code>, we define a <strong>0-indexed</strong> 2D matrix <code>p</code> of size <code>n * m</code> as the <strong>product</strong> matrix of <code>grid</code> if the following condition is met:</p>

<ul>
	<li>Each element <code>p[i][j]</code> is calculated as the product of all elements in <code>grid</code> except for the element <code>grid[i][j]</code>. This product is then taken modulo <code><font face="monospace">12345</font></code>.</li>
</ul>

<p>Return <em>the product matrix of</em> <code><font face="monospace">grid</font></code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,2],[3,4]]
<strong>Output:</strong> [[24,12],[8,6]]
<strong>Explanation:</strong> p[0][0] = grid[0][1] * grid[1][0] * grid[1][1] = 2 * 3 * 4 = 24
p[0][1] = grid[0][0] * grid[1][0] * grid[1][1] = 1 * 3 * 4 = 12
p[1][0] = grid[0][0] * grid[0][1] * grid[1][1] = 1 * 2 * 4 = 8
p[1][1] = grid[0][0] * grid[0][1] * grid[1][0] = 1 * 2 * 3 = 6
So the answer is [[24,12],[8,6]].</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[12345],[2],[1]]
<strong>Output:</strong> [[2],[0],[0]]
<strong>Explanation:</strong> p[0][0] = grid[0][1] * grid[0][2] = 2 * 1 = 2.
p[0][1] = grid[0][0] * grid[0][2] = 12345 * 1 = 12345. 12345 % 12345 = 0. So p[0][1] = 0.
p[0][2] = grid[0][0] * grid[0][1] = 12345 * 2 = 24690. 24690 % 12345 = 0. So p[0][2] = 0.
So the answer is [[2],[0],[0]].</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n == grid.length&nbsp;&lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= m == grid[i].length&nbsp;&lt;= 10<sup>5</sup></code></li>
	<li><code>2 &lt;= n * m &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= grid[i][j] &lt;= 10<sup>9</sup></code></li>
</ul>

from math import prod
class Solution:
    def constructProductMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        factors = [3,5,823]
        # 3, 5 and 823 are factors of 12345
        # every number inc product will be expressed in the form of s * 3**m * 5**n * 823**o
        # where s is coprime to 12345
        # for each i, j: p[i][j] reduced modulo 12345 is s * d' * 3**(m-m') * 5**(n-n') * 823**(o-o')
        # WHERE product of all numbers = s * 3**m * 5**n * 823**o AND grid[i][j] = d * 3**m' * 5**n' * 823**o'
        # and d' is multiploicative inverse of d modulo 12345
        # using theorem inverse of a mod number = a^{phi(a) - 1}.
        phi = prod([a-1 for a in factors])

        factorized = [[None for _ in range(len(grid[0]))] for _ in range(len(grid))]
        def factorize(num):
            # returns (s, [n,n,o]) where num = s * 3**m * 5**n * 823**o and  s is coprime to 12345
            exponents_ = [0] * (len(factors))
            # factors = [m, n, o] where num = s * 3**m * 5**n * 823**o and  s is coprime to 12345
            for (i,fac) in enumerate(factors):
                while not num%fac:
                    exponents_[i] += 1
                    num = num // fac
            return (num, exponents_)
        total_power = [0]*(len(factors))
        total_excess = 1
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                factorized[i][j] = factorize(grid[i][j])
                (s, exponents_) = factorized[i][j]
                total_excess = (total_excess * s)%12345
                for k in range(len(total_power)):
                    total_power[k] += exponents_[k]
        product_matrix = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                (s, exponents_) = factorized[i][j]
                product_matrix[i][j] = (pow(s, phi-1, 12345) * total_excess * prod([pow(fac, tot-cur, 12345) for (fac,tot,cur) in zip(factors, total_power, exponents_)]))%12345
        return product_matrix
        
            


        
70600