<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:
        rows, cols = len(pizza), len(pizza[0])
        
        # first, need way to query if a section contains an apple given a top left (r1, c1) and bottom right (r2, c2)
        # we can do this in constant time by keeping track of the number of apples above and to the left of any given cell
        apples = [[0] * cols for _ in range(rows)]
        for row in range(rows):
            apples_left = 0
            for col in range(cols):
                if pizza[row][col] == 'A':
                    apples_left += 1
                apples[row][col] = apples[row-1][col] + apples_left
              
        # query if there is an apple in this rectangle using the prefix sums
        def has_apple(r1, c1, r2 = rows-1, c2 = cols-1) -> bool:
            if r1 > r2 or c1 > c2:
                return False
            tot = apples[r2][c2]
            left_sub = apples[r2][c1-1] if c1 > 0 else 0
            up_sub = apples[r1-1][c2] if r1 > 0 else 0
            upleft_sub = apples[r1-1][c1-1] if r1 > 0 < c1 else 0
            in_rect = tot - left_sub - up_sub + upleft_sub
            return in_rect > 0
        
        # memory optimized dp, keep track of only one matrix of rows x cols
        # bc we only need to access the values at the previous number of cuts
        dp = [[1 if has_apple(r, c) else 0 for c in range(cols + 1)] for r in range(rows + 1)]
        
        for cuts in range(1, k):
            new_dp = [[0] * (cols + 1) for _ in range(rows + 1)]
            for row in range(rows-1, -1, -1):
                for col in range(cols-1, -1, -1):
                    
                    for r2 in range(row, rows):
                        if has_apple(row, col, r2):
                            new_dp[row][col] += dp[r2+1][col]
                            
                    for c2 in range(col, cols):
                        if has_apple(row, col, rows-1, c2):
                            new_dp[row][col] += dp[row][c2+1]
            dp = new_dp
                            
        return dp[0][0] % (10**9 + 7)
17000