Given an grid, count how many ways you can tile it completely using and dominoes. Both dimensions can be up to , and the answer can be huge, so report it modulo .
For example, a grid has tilings: all horizontal, all vertical, or mixed. You need to count these systematically without missing or double-counting any. This is the canonical broken profile problem. Before reading the solution, think: how would you track which cells are filled as you go column by column?