Assume you could calculate the number of different paintings for a rectangle with c columns and r rows where the first r-1 rows are completely filled and the last row has any of 2c possible patterns. Then, by trying all variations of filling the last row where small rectangles may be spilled into a further row, you can calculate the number of different paintings for a rectangle with r+1 rows where the first r rows are completely filled and the last row again has any pattern. 

This straightforwardly leads to a dynamic programming solution. All possible ways of filling a row part of which may already be occupied and spilling into the next row creating a new pattern are genrated by backtracking over a row. Viewing these as transitions from a pattern to another pattern, their number is given by the recursive equation Tc = 2 Tc-1 + Tc-2. Its solution is asymptotically exponential with a base of sqrt(2)+1, which is not a problem for c<=11. 

If both h and w are odd, the result is 0. Since the number of paintings is a symmetric function, the number of columns should be chosen as the smaller of the two input numbers whenever possible to improve run-time behaviour substantially. 

Judges' test data includes all 121 legal combinations of h and w.