Prerequisites: Dynamic Programming, Bit masking Consider the following problem. Problem: In how many ways can you fill an \(n \times m\) board with \(2 \times 1\) dominoes such that whole board is covered and no two dominoes overlap with each other? Constraints: \(1 \leq n \leq 9\) \(1 \leq m \leq 1000\) Solution: One way of solving this problem is to obtain a recurrence relation for a given \(n\) in terms of \(m\). For example, if \(n = 2\), we get the recurrence relation \[f_{m} = f_{m-1} + f_{m-2}\] And if \(n = 3\), we get the recurrence relation \[f_{m} = 4f_{m-1} - f_{m-2}\] Click here for detailed explanation on above recurrence relations. But obtaining recurrence relation becomes harder as \(n\) increases. So, instead we shall approach this problem in a different way. Let us define profile of some column as an n-bit binary integer which gives information of the occupancy of blo