My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too. Or just jump to my GitHub repository.

The code contains #ifdefs to switch between the original problem and the Hackerrank version.
Enable #ifdef ORIGINAL to produce the result for the original problem (default setting for most problems).

       
#include <iostream>
       
#include <unordered_map>
       
 
       
#define ORIGINAL
       
 
       
// grid size

       
unsigned int height = 9;
       
unsigned int width  = 2;
       
 
       
// indicate an empty row

       
const unsigned int EmptyRow = 0;
       
 
       
// set a certain bit to one (= position is not available anymore), return true if bit was zero
       
// note: second parameter is an in/out parameter

       
bool use(unsigned int pos, unsigned int& row)
       
{
       
  unsigned int mask = 1 << pos;
       
  bool result = (row & mask) == 0;
       
  row |= mask;
       
  return result;
       
}
       
 
       
// recursive search

       
unsigned long long search(unsigned int rowsLeft,
       
                          unsigned int rowA, unsigned int rowB, unsigned int rowC)
       
{
       
  // done ?
       
  if (rowsLeft == 0)
       
    return 1;
       
 
       
  // filled another row ?
       
  unsigned int fullRow = (1 << width) - 1;
       
  if (rowA == fullRow)
       
    return search(rowsLeft - 1, rowB, rowC, EmptyRow);
       
 
       
  // find first gap in rowA
       
  unsigned int pos = 0;
       
  while ((rowA & (1 << pos)) != 0)
       
    pos++;
       
 
       
  // unique ID
       
  unsigned long long hash; // unsigned int would suffice for grid with up to 9 columns, too
       
  hash   = rowsLeft;
       
  hash <<= width;
       
  hash  |= rowA;
       
  hash <<= width;
       
  hash  |= rowB;
       
  hash <<= width;
       
  hash  |= rowC;
       
 
       
  // about twice as fast as std::map
       
  static std::unordered_map<unsigned long long, unsigned long long> cache;
       
  auto i = cache.find(hash);
       
  if (i != cache.end())
       
    return i->second;
       
 
       
  unsigned long long result = 0;
       
 
       
  // shape: ##
       
  //        #
       
  unsigned int a = rowA;
       
  unsigned int b = rowB;
       
  unsigned int c = rowC;
       
  if (rowsLeft >= 2 && pos < width - 1 &&
       
      use(pos, a) && use(pos + 1, a) && use(pos, b))
       
    result += search(rowsLeft, a, b, c);
       
 
       
  // shape: ##
       
  //         #
       
  a = rowA; b = rowB; //c = rowC;
       
  if (rowsLeft >= 2 && pos < width - 1 &&
       
      use(pos, a) && use(pos + 1, a) && use(pos + 1, b))
       
    result += search(rowsLeft, a, b, c);
       
 
       
  // shape: #
       
  //        ##
       
  a = rowA; b = rowB; //c = rowC;
       
  if (rowsLeft >= 2 && pos < width - 1 &&
       
      use(pos, a) && use(pos, b) && use(pos + 1, b))
       
    result += search(rowsLeft, a, b, c);
       
 
       
  // shape:  #
       
  //        ##
       
  // note: this shape extends one "negative" unit to the left
       
  a = rowA; b = rowB; //c = rowC;
       
  if (rowsLeft >= 2 && pos > 0 && pos < width &&
       
      use(pos, a) && use(pos - 1, b) && use(pos, b))
       
    result += search(rowsLeft, a, b, c);
       
 
       
  // shape:  #
       
  //         #
       
  //         #
       
  a = rowA; b = rowB; //c = rowC;
       
  if (rowsLeft >= 3 && pos < width &&
       
      use(pos, a) && use(pos, b) && use(pos, c))
       
    result += search(rowsLeft, a, b, c);
       
 
       
  // shape: ###
       
  a = rowA; b = rowB; c = rowC;
       
  if (rowsLeft >= 1 && pos < width - 2 &&
       
      use(pos, a) && use(pos + 1, a) && use(pos + 2, a))
       
    result += search(rowsLeft, a, b, c);
       
 
       
#ifndef ORIGINAL
       
  result %= 1000000007; // Hackerrank only
       
#endif
       
 
       
  // memoize
       
  cache[hash] = result;
       
  return result;
       
}
       
 
       
int main()
       
{
       
  // read grid size
       
  std::cin >> width >> height;
       
 
       
  // prefer fewer columns
       
  if (width > height)
       
    std::swap(width, height);
       
 
       
  // let's go !
       
  std::cout << search(height, EmptyRow, EmptyRow, EmptyRow) << std::endl;
       
  return 0;
       
}

This solution contains 21 empty lines, 27 comments and 5 preprocessor commands.