For example, consider H=3. There are four ways to start. First, the boring one:

111
222
333
444
555

Clearly, if we pick this one, we are just constructing the rest of the tiling by
solving the same problem for a (2H-1)*(W-H) rectangle.

Now, the other three:

1
1
1
222
333

222
1
1
1
333

222
333
1
1
1

Let's pick any of these. How can we continue? Consider the first non-complete column and
the first cell in this column. We can either cover it vertically:

222
333
14
14
14

Or horizontally:

222
333
1444
1
1

But if we choose the horizontal option, we are, once again, forced to put a horizontal tile into
each of the other rows:

222555
333666
1444
1777
1888

and that again decreased the width of the untiled part by H while preserving the shape of the
"coastline".

Thus, there are only very few reachable states. For each x, there are the states where exactly
K consecutive rows have length x, and all other rows have length K*ceil(x/K). Now let dp[x]
be the number of ways to reach such a state. We can set up a simple forward-counting dynamic
programming solution:

long[] dp = new long[W*2];
dp[0] = 1;
for (int i = 0; i < W; i++) {
        int x = 1;
        if (i%H == 0) x = H;
        dp[i+H] = dp[i];
        dp[i+1] = (dp[i+1]+dp[i]*x)%mod;
}
return (int)dp[W];

Other solutions are possible as well. There are other ways to write a good recurrence, and for small H 
and large W we can even use matrix multiplication to evaluate the recurrence more efficiently.