Leetcode 1444. Number of Ways of Cutting a Pizza

Count the number of ways to make k-1 axis-aligned cuts on a rows×cols grid of 'A' (apple) and '.' so that each of the k resulting pieces contains at least one apple, modulo 10^9+7. With rows,cols ≤50 and k ≤10 this is typically solved using DP over subgrids combined with prefix sums to quickly check valid cuts.