<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 __init__(self):
        self.rows =0
        self.cols = 0
        self.apples =[]
        self.MOD = 10**9 + 7
        self.dp ={}

    
    def n_ways_pizza_cut(self,r,c,k):
        if self.apples[r][c] < k:
            return 0
        
        if k==1:
            return 1 if self.apples[r][c] >=1 else 0
        
        dp_idx = (r,c,k)
        if dp_idx in self.dp:
            return self.dp[dp_idx]

        self.dp[dp_idx] =0
        # Horizontal Cut
        for h in range(r+1,self.rows):
            lower_slice = self.apples[h][c]
            upper_slice = self.apples[r][c] - lower_slice

            if lower_slice >=k-1 and upper_slice >= 1:
                self.dp[dp_idx] = (self.dp[dp_idx] + self.n_ways_pizza_cut(h,c,k-1))%self.MOD
        
        # Vertical Slice
        for v in range(c+1,self.cols):
            right_slice = self.apples[r][v]
            left_slice = self.apples[r][c] - right_slice

            if left_slice >=1 and right_slice >=k-1:
                self.dp[dp_idx]= (self.dp[dp_idx] + self.n_ways_pizza_cut(r,v,k-1))%self.MOD
        
        return self.dp[dp_idx]

                
    def ways(self, pizza: List[str], k: int) -> int:
        self.rows = len(pizza)
        self.cols = len(pizza[0])

        self.apples = [[0 for _ in range(self.cols)] for _ in range(self.rows)]

        for i in range(self.rows-1,-1,-1):
            for j in range(self.cols-1,-1,-1):
                self.apples[i][j] = self.apples[i][j+1] if  j+1 <self.cols else 0
                
                for l in range(i,self.rows):
                    if pizza[l][j] == 'A':
                        self.apples[i][j]+=1
        
        return self.n_ways_pizza_cut(0,0,k)


        
18300