<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>

from typing import List

class Solution:
    def ways(self, pizza: List[str], k: int) -> int:
        MOD = 10**9 + 7
        rows, cols = len(pizza), len(pizza[0])  # Corrected to use pizza[0] for column length

        # Create the prefix sum matrix
        prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
        
        # Fill the prefix sum matrix
        for r in range(rows):
            for c in range(cols):
                prefix[r+1][c+1] = (1 if pizza[r][c] == 'A' else 0) + \
                                   prefix[r][c+1] + prefix[r+1][c] - prefix[r][c]
        
        # Function to check if there is at least one apple in the submatrix
        def hasApple(r1, c1, r2, c2):
            # Number of apples in the submatrix (r1, c1) to (r2-1, c2-1)
            return (prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]) > 0
        
        # Recursive helper function with memoization
        cache = {}
        def helper(r, c, r2, c2, k):
            # Base case: if k == 1, check if the current slice has any apples
            if k == 1:
                return 1 if hasApple(r, c, r2, c2) else 0
            
            # Check if the result is already cached
            if (r, c, r2, c2, k) in cache:
                return cache[(r, c, r2, c2, k)]
            
            # If no apples in the submatrix, return 0
            if not hasApple(r, c, r2, c2):
                cache[(r, c, r2, c2, k)] = 0
                return 0
            
            # Try making all possible horizontal and vertical cuts
            cuts = 0
            
            # Horizontal cuts: try cutting between rows
            for cutR in range(r + 1, r2 + 1):
                if hasApple(r, c, cutR - 1, c2):
                    cuts = (cuts + helper(cutR, c, r2, c2, k - 1)) % MOD
            
            # Vertical cuts: try cutting between columns
            for cutC in range(c + 1, c2 + 1):
                if hasApple(r, c, r2, cutC - 1):
                    cuts = (cuts + helper(r, cutC, r2, c2, k - 1)) % MOD
            
            # Cache the result
            cache[(r, c, r2, c2, k)] = cuts
            return cuts
        
        # Start recursion from the full pizza
        return helper(0, 0, rows - 1, cols - 1, k)

18700