<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:
        
        table = []
        for i in range (0, len(pizza)):
            table.append([0]*len(pizza[0]))
        
        for i in range (0, len(pizza)):
            curr =0 
            for j in range (0, len(pizza[0])):
                curr += int(pizza[i][j]=='A') 
                table[i][j] = curr + (table[i-1][j] if i>=1 else 0)
        
        
        def check (r1, c1, r2, c2):
            if (r1 > r2 or c1 > c2 ): return 0 
            return (table[r2][c2] - (table [r1-1][c2] if r1 >0 else 0)  
                                -(table[r2][c1-1] if c1>0 else 0) 
                                +(table[r1-1][c1-1] if r1>0 and c1> 0 else 0))
            
        
        MOD = 10**9 + 7
        memo = dict()

        @lru_cache(None)
        def recurse (r1, c1, r2, c2, k):
            if (r1 > r2 or c1 > c2 ): return 0 
            elif k==1: 
                if check(r1, c1, r2, c2) > 0:
                    return 1
                else:
                    return 0
            elif k==0: return 0
            elif (r1,c1,r2,c2,k) in memo:
                return memo[(r1,c1,r2,c2,k)]
            
            memo[(r1,c1,r2,c2,k)] = 0
            for i in range (c1, c2):
                left = check(r1, c1, r2, i) 
                right = check(r1, i+1, r2, c2)
                if (left >=1 and right >= k-1):
                     memo[(r1,c1,r2,c2,k)] += recurse(r1, i+1, r2, c2, k-1)
            
            for i in range (r1, r2):
                left = check(r1, c1, i, c2) 
                right = check(i+1, c1, r2, c2)
                if (left >=1 and right >= k-1):
                     memo[(r1,c1,r2,c2,k)] += recurse(i+1, c1, r2, c2, k-1)
            memo[(r1,c1,r2,c2,k)] =  memo[(r1,c1,r2,c2,k)] % MOD
            return memo[(r1,c1,r2,c2,k)]
        
        return recurse(0,0,len(pizza)-1, len(pizza[0])-1, k)
21000