<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:
        #m = rows
        #n = cols
        MOD = 10 ** 9 +7
        m = len(pizza)
        n = len(pizza[0])
        #apple_count[i][j] := # of apple from i, j to (m, n)
        apple_count = [[0] * n for _ in range(m)]
        apple_count[m-1][n-1] = 1 if pizza[m-1][n-1] =='A' else 0
        for i in range(m-2, -1, -1):
            apple_count[i][n-1] = apple_count[i+1][n-1] + (1 if pizza[i][n-1] == 'A' else 0)
        for j in range(n-2, -1, -1):
            apple_count[m-1][j] = apple_count[m-1][j+1] + (1 if pizza[m-1][j] == 'A' else 0)
        for i in range(m-2, -1, -1):
            for j in range(n-2, -1, -1):
                apple_count[i][j] = (1 if pizza[i][j] == 'A' else 0) + apple_count[i+1][j] + \
                                    apple_count[i][j+1] - \
                                    apple_count[i+1][j+1]
        print(apple_count)

        dp = [[[0] * n for _ in range(m)] for _ in range(k)]
        
        coord_list = set()

        for i in range(0, m):
            for j in range(max(k-1-i,0), n):
                if apple_count[i][j] > 0:
                    coord_list.add((i, j))
                    dp[k-1][i][j] = 1
        
        #print(coord_list)
        for c in range(k-2, -1, -1):
            next_coord_list = set()
            for i, j in coord_list:
                for ni in range(i-1, -1, -1):
                    if ni + j < c:
                        break
                    if apple_count[ni][j] - apple_count[i][j] > 0:

                        dp[c][ni][j] += dp[c+1][i][j]
                        dp[c][ni][j] %= MOD
                        #if ni == 3 and j == 0:
                            #print(c, ni, j, dp[c][ni][j])
                        next_coord_list.add((ni, j))

                for nj in range(j-1, -1, -1):
                    if i + nj < c:
                        break
                    if apple_count[i][nj] - apple_count[i][j] > 0:

                        dp[c][i][nj] += dp[c+1][i][j]
                        dp[c][i][nj] %= MOD
                        #if i == 3 and nj == 0:
                            #print(c, i, nj, dp[c][i][nj])
                        next_coord_list.add((i, nj))
                #print(c, i, j, dp[1][3][0])
            coord_list = next_coord_list
            #print(coord_list)

        #print(dp[1][3][0])
        return dp[0][0][0]%MOD
18000