<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:
        self.r = len(pizza)
        self.c = len(pizza[0])
        
        tot_apples = 0
        self.pfsum_row = []
        self.pfsum_col = []
        for i in range(self.r):
            pfr = 0
            pfs_r = [0] * self.c
            pfs_c = [0] * self.c
            for j in range(self.c):
                if i > 0:
                    pfs_c[j] += self.pfsum_col[i - 1][j]
                if pizza[i][j] == 'A':
                    pfr += 1
                    pfs_c[j] += 1
                    tot_apples += 1
                pfs_r[j] = pfr
            self.pfsum_row.append(pfs_r)
            self.pfsum_col.append(pfs_c)
        
        if tot_apples < k:
            return 0
        
        if k == 1:
            return 1
        return self.getWays(0, 0, k) % (1000000007)
    
    
    @cache
    def getWays(self, i, j, k):
        if k == 1:
            found = False
            for c in range(j, self.c):
                apple_in_region = self.pfsum_col[self.r - 1][c]
                if i > 0:
                     apple_in_region -= self.pfsum_col[i - 1][c]
                if apple_in_region:
                    found = True
                    break
            if found:
                return 1   
            return 0
        else:
            cannot_cut = True
            nr = i
            t_cnt = 0
            while nr < self.r - 1:
                while nr < self.r - 1 and cannot_cut:
                    apple_in_region = self.pfsum_row[nr][self.c - 1]
                    if j > 0:
                        apple_in_region -= self.pfsum_row[nr][j - 1]
                    if apple_in_region:
                        cannot_cut = False
                    else:
                        nr += 1
                        
                if nr < self.r - 1:
                    t_cnt += self.getWays(nr + 1, j, k - 1)
                nr += 1
                
            cannot_cut = True
            nc = j
            while nc < self.c - 1:
                while nc < self. c - 1 and cannot_cut:
                    apple_in_region = self.pfsum_col[self.r - 1][nc]
                    if i > 0:
                        apple_in_region -= self.pfsum_col[i - 1][nc]
                    if apple_in_region:
                        cannot_cut = False
                    else:
                        nc += 1
                
                if nc < self.c - 1:
                    t_cnt += self.getWays(i, nc + 1, k - 1)
                nc += 1
            
            return t_cnt
19400