<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:
        """
        [1,0,0,1,1,1] K=4 ANS=1
       [0,1,1,1,2,3,4]
       c+=1


       [1,0,1] k=2  ans=3
       [0,1,0] k=3 ans=2
       [0,0,0]

        0,1,1,2
        0,0,1,1
        0,0,0,0

        0,1,1,2 k=2
        0,1,2,3 
        0,1,2,3
        """ 
      

        def pizza_in_this_sq(s,e):
            for i in range(s[0],e[0]):
                for j in range(s[1],e[1]):
                    if pizza[i][j]=='A':
                        return True

            return False
        hashmap={}
        @cache
        def cut_pizza(start,end,k):
            nonlocal hashmap
            if (start,end) in hashmap:
                return hashmap[(start,end)]
            if not pizza_in_this_sq(start,end):
                return 0
            if k==0:
                return 1

            #vertical
            count=0
            for i in range(start[1]+1,end[1]):
                if pizza_in_this_sq(start,(end[0],i)):
                    count+=cut_pizza((start[0],i),end,k-1)
                    count%=MOD
            
            #horizontal
            for j in range(start[0]+1,end[0]):
                if pizza_in_this_sq(start,(j,end[1])):
                    count+=cut_pizza((j,start[1]),end,k-1)
                    count%=MOD
            hashmap={(start,end):count}
            return count








        n=len(pizza)
        m=len(pizza[0])
        MOD=10**9 + 7
                        
        return cut_pizza((0,0),(n,m),k-1)%MOD
19600