<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 {
public:
    int ways(vector<string>& pizza, int k) {
        const int MOD = 1000000007;
        int rows = pizza.size(), cols = pizza[0].size();
        
        // Create a prefix sum array
        vector<vector<int>> prefix(rows + 1, vector<int>(cols + 1, 0));
        for (int i = 1; i <= rows; ++i) {
            for (int j = 1; j <= cols; ++j) {
                prefix[i][j] = (pizza[i - 1][j - 1] == 'A' ? 1 : 0)
                             + prefix[i - 1][j] + prefix[i][j - 1]
                             - prefix[i - 1][j - 1];
            }
        }
        
        // Check if there are apples in the specified region
        auto hasApple = [&](int x1, int y1, int x2, int y2) {
            return (prefix[x2 + 1][y2 + 1] - prefix[x1][y2 + 1] - prefix[x2 + 1][y1] + prefix[x1][y1]) > 0;
        };

        // Memoization for DP results
        int dp[51][51][11]; // Considering the maximum constraints
        memset(dp, -1, sizeof(dp));
        
        // Define the dp function
        function<int(int, int, int)> solve = [&](int x, int y, int p) {
            if (p == 1)
                return hasApple(x, y, rows - 1, cols - 1) ? 1 : 0;
            if (dp[x][y][p] != -1)
                return dp[x][y][p];
            
            int ways = 0;
            // Horizontal cuts
            for (int i = x + 1; i < rows; ++i) {
                if (hasApple(x, y, i - 1, cols - 1))
                    ways = (ways + solve(i, y, p - 1)) % MOD;
            }
            // Vertical cuts
            for (int j = y + 1; j < cols; ++j) {
                if (hasApple(x, y, rows - 1, j - 1))
                    ways = (ways + solve(x, j, p - 1)) % MOD;
            }
            
            return dp[x][y][p] = ways;
        };
        
        return solve(0, 0, k);
    }
};
10600