<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:
        MODULE = 1000000007
        m = len(pizza)
        n = len(pizza[0])
        # F = [[[0 for l in range(n)] for j in range(m)] for i in range(k)]
        G = [[[0 for l in range(n)] for j in range(m)] for i in range(2)]
        a = [[0 for j in range(n)] for i in range(m)]
        s = [[0 for j in range(n)] for i in range(m)]
        index = 0
        for i in range(m):
            for j in range(n):
                a[m-1-i][n-1-j] = 1 if pizza[i][j] == 'A' else 0
        # for i in range(m):
        #     print(a[i])
        s[0][0] = a[0][0]
        G[index][0][0] = s[0][0]
        for i in range(1, m):
            s[i][0] = s[i-1][0] + a[i][0]
            if s[i][0] > 0:
                G[index][i][0] = 1
        for j in range(1, n):
            s[0][j] = s[0][j-1] + a[0][j]
            if s[0][j] > 0:
                G[index][0][j] = 1
        for i in range(1, m):
            for j in range(1, n):
                s[i][j] = s[i-1][j] + s[i][j-1] + a[i][j] - s[i-1][j-1]
                if s[i][j] > 0:
                    G[index][i][j] = 1

        for l in range(1, k):
            index = 1 - index
            for i in range(m):
                for j in range(n):
                    G[index][i][j] = 0
                    for j1 in range(j):
                        if s[i][j] - s[i][j1] > 0:
                            G[index][i][j] = (G[index][i][j] % MODULE + G[1-index][i][j1] % MODULE) % MODULE
                    for i1 in range(i):
                        if s[i][j] - s[i1][j] > 0:
                            G[index][i][j] = (G[index][i][j] % MODULE + G[1-index][i1][j] % MODULE) % MODULE
            
        # for l in range(0, k ):
        #     for i in range(m):
        #         s = ''
        #         for j in range(n):
        #             s += str(F[l][i][j]) + ', '
        #         print(s)
        #     print(l, '-------------------')
        return G[index][m-1][n-1]
16700