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

    _table = {}

    def ways(self, pizza: List[str], k: int) -> int:
        self._table.clear()
        count = self.sub(pizza, k - 1, 0, 0)
        return count % (10 ** 9 + 7)

    def sub(self, pizza: List[str], remcuts: int, top: int, left: int) -> int:
        # print(top, left, remcuts)
        # print(self._table)
        # early cancel, check if we've already calc'd it
        cachedVal = self._table.get((top, left, remcuts))
        if cachedVal != None:
            return cachedVal

        # base case
        # if no more cuts remaining, check if any apples left
        # if yes, it's a valid way and return 1
        # else return 0
        if (remcuts == 0):
            for row in range(top, len(pizza)):
                for col in range(left, len(pizza[row])):
                    if (pizza[row][col] == 'A'):
                        self._table[(top, left, 0)] = 1
                        return 1

            # No apples found
            self._table[(top, left, 0)] = 0
            return 0

        # Now, for each cell we build the table down:
        # We make cuts across each column or across each row
        total_ways = 0
        apple_retained = False
        for row in range(1, len(pizza) - top):
            # Should only subdivide here if the retained part has an apple
            if (not apple_retained):
                for col in range(left, len(pizza[row])):
                    if pizza[top + row - 1][col] == 'A':
                        apple_retained = True
                        # print("Found apple at ", top+row -1 , col)
                        break

            if apple_retained:
                total_ways += self.sub(pizza, remcuts - 1, top + row, left)

        apple_retained = False
        for col in range (1, len(pizza[top]) - left):
            # Should only subdivide here if the retained part has an apple
            if (not apple_retained):
                for row in range(top, len(pizza)):
                    if pizza[row][left + col - 1] == 'A':
                        apple_retained = True
                        break

            if apple_retained:
                total_ways += self.sub(pizza, remcuts - 1, top, left + col)
        
        self._table[(top, left, remcuts)] = total_ways
        return total_ways

            
18200