cake: 'A' marks a cell with a berry and '.' an empty cell. You need to cut the cake into pieces pieces using pieces - 1 cuts.
Each cut runs along cell boundaries across the whole remaining part, either vertically or horizontally. After a vertical cut, the left part goes to a guest; after a horizontal cut, the top part does. You keep cutting what is left, and the final remaining part goes to the last guest.
Count the ways to cut the cake so that every piece has at least one berry. Two ways differ if some step uses a different cut. The answer can be large, so return it modulo 10⁹ + 7.cake=["A.A", "...", ".A."], pieces=2 → 4
Four cuts work: vertical after column 0 or column 1, and horizontal after row 0 or row 1; each time both parts contain a berry.
cake=["AA", ".."], pieces=3 → 0
There are only two berries for three pieces, so there is no way.
cake=["A"], pieces=1 → 1
cake=["A.A", "...", ".A."], pieces=2
4
Run checks the first 3 tests in your browser. Submit checks all 73 tests on the server, hidden ones included.