## Description

Your exceedingly wealthy uncle, Sir Capitus Tet, from whom you eventually hope to

obtain a significant inheritance has asked for your help with a problem. He has in his

possession a large supply of various carpet pieces – each consists of four squares joined

side to side, and they are in various colours as shown below. He also has, in his vast

mansion, various hallways which he’d like to carpet by sewing the pieces together side

to side to form an unbroken rectangle. As a matter of intellectual curiosity, he would

like to know – given the dimension of a carpet (measured in units of the squares that

make up the individual pieces), how many different ways are there to fit together some

pieces to form such a carpet?

The carpet pieces:

A completed carpet of width 4 and length 6:

For these purposes, two carpets are considered different if they look different from the

perspective of an observer at one end. That is, a carpet will (generally, though not

always) be different from its rotation by 180 degrees. As seen in the example, pieces

can be rotated, though of course they can’t be flipped over.

Task

This task uses the standard input/output format. A scenario consists of two numbers

– a width (which will be at most 6 squares) and a length (at most 100 squares). The

output for the scenario is the exact number of possible carpets of that width and length.

COSC 326 2017 Semester 2 Etude 9 ´

This may well require extended precision arithmetic (i.e., the answer may not fit in a

standard machine-sized integer), and you may use libraries such as BigInteger to

allow for this (or your own package from etude 8).