<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) {
        /*
            dp[i][j][remain] = number of ways to cut pizza[i: r][j: c] with remain cuts
            dp[i][j][remain] = sum(dp[r][c][remain-1]) if dp[r][c] is valid for cut
        */
        int mod = 1e9+7;
        int m = pizza.size();
        int n = pizza[0].size();
        int dp[m][n][k];
        int apple[m+1][n+1];
        int prefix_sum_of_dp_row[m];
        int prefix_sum_of_dp_column[n];
        memset(dp, 0, sizeof(dp));
        memset(apple, 0, sizeof(apple));
        memset(prefix_sum_of_dp_column, 0, sizeof(prefix_sum_of_dp_column));
        memset(prefix_sum_of_dp_row, 0, sizeof(prefix_sum_of_dp_row));
        
        for(int r=m-1; r>=0; r--){
            for(int c=n-1; c>=0; c--){
                apple[r][c] = (pizza[r][c]=='A' ?1 :0) + apple[r+1][c] +　apple[r][c+1] - apple[r+1][c+1];
                dp[r][c][0] = (apple[r][c]>0 ?1 :0);
            }
        }
        for(int remain=1; remain<k; remain++){
            for(int r=0; r<m; r++){
                for(int c=0; c<n; c++){
                    for(int next_r=r+1; next_r<m; next_r++){
                        if(apple[r][c]-apple[next_r][c]>0){
                            dp[r][c][remain] = (dp[r][c][remain] + dp[next_r][c][remain-1])%mod;
                        }
                    }
                    for(int next_c=c+1; next_c<n; next_c++){
                        if(apple[r][c]-apple[r][next_c]>0){
                            dp[r][c][remain] = (dp[r][c][remain] + dp[r][next_c][remain-1])%mod;
                        }
                    }
                }
            }
        }
        return dp[0][0][k-1];
    }
};
8900