<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:
    #define ll long long 
    const int mod = 1e9+7;
    
    ll f(int row, int col, int k, vector<vector<int>> &pre, vector<vector<vector<ll>>>& dp) {
        int n = pre.size() - 1;
        int m = pre[0].size() - 1;
    
        int rem = pre[n][m] - pre[row][m] - pre[n][col] + pre[row][col];

        if (rem == 0)
            return 0;
        
        // Base case: if no more cuts are needed, this is a valid partition
        if (k == 0)
            return 1;
        
        // Check if the value is already computed (memoization)
        if (dp[row][col][k] != -1)
            return dp[row][col][k];
        
        ll ans = 0;
        
        // Try vertical cuts (cutting rows)
        for (int i = row + 1; i < n; i++) {
            // Check if the top submatrix (from row to i-1) has at least one apple
            int topApples = pre[i][m] - pre[row][m] - pre[i][col] + pre[row][col];
            if (topApples > 0 && pre[n][m]-topApples>=k-1) {
                ans += f(i, col, k - 1, pre, dp);
                ans %= mod;
            }
        }
        
        // Try horizontal cuts (cutting columns)
        for (int j = col + 1; j < m; j++) {
            // Check if the left submatrix (from col to j-1) has at least one apple
            int leftApples = pre[n][j] - pre[row][j] - pre[n][col] + pre[row][col];
            if (leftApples > 0 && pre[n][m]-leftApples>=k-1) {
                ans += f(row, j, k - 1, pre, dp);
                ans %= mod;
            }
        }
        
        return dp[row][col][k] = ans;
    }
    
    int ways(vector<string>& pizza, int k) {
        int n = pizza.size();
        int m = pizza[0].length();
        
        // Precompute the prefix sum array
        vector<vector<int>> pre(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + (pizza[i-1][j-1] == 'A');
            }
        }
        
        // Initialize dp array with -1 (indicating not computed)
        vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(m + 1, vector<ll>(k, -1)));
        
        return f(0, 0, k - 1, pre, dp);
    }
};

10500