<p>Given a rectangular pizza represented as a <code>rows x cols</code>&nbsp;matrix containing the following characters: <code>&#39;A&#39;</code> (an apple) and <code>&#39;.&#39;</code> (empty cell) and given the integer <code>k</code>. You have to cut the pizza into <code>k</code> pieces using <code>k-1</code> cuts.&nbsp;</p>

<p>For each cut you choose the direction: vertical or horizontal, then you choose a cut position at the cell boundary and cut the pizza into two pieces. If you cut the pizza vertically, give the left part of the pizza to a person. If you cut the pizza horizontally, give the upper part of the pizza to a person. Give the last piece of pizza to the last person.</p>

<p><em>Return the number of ways of cutting the pizza such that each piece contains <strong>at least</strong> one apple.&nbsp;</em>Since the answer can be a huge number, return this modulo 10^9 + 7.</p>

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

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2020/04/23/ways_to_cut_apple_1.png" style="width: 500px; height: 378px;" /></strong></p>

<pre>
<strong>Input:</strong> pizza = [&quot;A..&quot;,&quot;AAA&quot;,&quot;...&quot;], k = 3
<strong>Output:</strong> 3 
<strong>Explanation:</strong> The figure above shows the three ways to cut the pizza. Note that pieces must contain at least one apple.
</pre>

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

<pre>
<strong>Input:</strong> pizza = [&quot;A..&quot;,&quot;AA.&quot;,&quot;...&quot;], k = 3
<strong>Output:</strong> 1
</pre>

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

<pre>
<strong>Input:</strong> pizza = [&quot;A..&quot;,&quot;A..&quot;,&quot;...&quot;], k = 1
<strong>Output:</strong> 1
</pre>

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

<ul>
	<li><code>1 &lt;= rows, cols &lt;= 50</code></li>
	<li><code>rows ==&nbsp;pizza.length</code></li>
	<li><code>cols ==&nbsp;pizza[i].length</code></li>
	<li><code>1 &lt;= k &lt;= 10</code></li>
	<li><code>pizza</code> consists of characters <code>&#39;A&#39;</code>&nbsp;and <code>&#39;.&#39;</code> only.</li>
</ul>

class Solution:
    
    def ways(self, pizza: List[str], k: int) -> int:
        if sum([sum([1 if col=="A" else 0 for col in row]) for row in pizza]) == 0:
            return 0
        if k == 1:
            return 1
        self.m, self.n, self.total_cut = len(pizza), len(pizza[0]), k - 1
        self.dp = [[[0 for i in range(self.total_cut)] for i in range(self.n)] for i in range(self.m)]
        self.digital_pizza = [[1 if pizza[i][j]=="A" else 0 for j in range(self.n)] for i in range(self.m)]
        self.sum_row_postfix = [[sum(self.digital_pizza[i][j:]) for j in range(self.n)] for i in range(self.m)]
        self.sum_col_postfix = [[sum([row[j] for row in self.digital_pizza[i:]]) for j in range(self.n)] for i in range(self.m)]
        self.dp = {}
        return self.recursive(0, 0, 0)

    def recursive(self, pr, pc, cur_cut):
        if (pr, pc, cur_cut) in self.dp.keys():
            return self.dp[(pr, pc, cur_cut)]
        # print(pr, pc, cur_cut)
        if pr >= self.m or pc >= self.n:
            return 0

        if cur_cut == self.total_cut:
            return 1 if sum(self.sum_col_postfix[pr][pc:]) > 0 else 0

        if pr >= self.m - 1 and pc >= self.n - 1:
            return 0

        result = 0
        for i in range(1, self.m - pr):
            if sum([sum(row[pc : ]) for row in self.digital_pizza[pr : pr + i]]) > 0:
                result += self.recursive(pr + i, pc, cur_cut + 1)

        for i in range(1, self.n - pc):
            if sum([sum(row[pc : pc + i]) for row in self.digital_pizza[pr : ]]) > 0:
                result += self.recursive(pr, pc + i, cur_cut + 1)
        result = result % int(10e8 + 7)
        self.dp[(pr, pc, cur_cut)] = result
        return result
17800