# Problem D

Pavers

In the land of *Quendor*, walkways, sidewalks and
hallways are always $2$
*mb* (*mini-bloit*, roughly $\frac{1}{2000}$ of a *bloit*)
in width. J. Pierpont Flathead (pictured to the right) has
hired the *Frobozz Magic Paver Company* to install new
walkways in and around all his banks using pavers. Given the
huge number of walkways found at each bank, and the
eccentricity of Flathead, *Frobozz* decided to write a
program to determine how many different ways there are to
completely cover a walkway using pavers that are $1$mb-by-$1$mb squares, $2$mb-by-$1$mb rectangles in either orientation
and right (or L-shaped) tromino pavers in any of the four
possible orientations shown below. This list would then be
presented to Flathead so he could choose the patterns he
wanted.

You will help write this program for *Frobozz*. Your
program must find the total number of tilings and the total
number of each paver type used in those tilings. For instance,
there are two tilings of a $2$-by-$1$ walkway using a total of two
$1$-by-$1$ square pavers and one $2$-by-$1$ rectangular paver.

For a $2$-by-$2$ rectangle, there are $11$ tilings using a total of $16$ $1$-by-$1$ square pavers, $8$ $2$-by-$1$ rectangular pavers and $4$ tromino pavers.

Write a program which takes as input the length $n$ (in *mb*) of a $2$-by-$n$ walkway and outputs the number of
tilings by combinations of the three paver types as well as the
total number of each type of paver used.

## Input

Input consists of a single number $n$ representing the decimal length $n$ of the walkway. The values of $n$ will be chosen so that all of the output values will fit in a $32$-bit unsigned integer.

## Output

Output four decimal integers separated by a single space: the total number of tilings of a $2$-by-$n$ walkway, the total number of $1$-by-$1$ square pavers used, the total number of $1$-by-$2$ rectangular pavers used and the total number of tromino pavers used for these tilings.

Sample Input 1 | Sample Output 1 |
---|---|

1 |
2 2 1 0 |

Sample Input 2 | Sample Output 2 |
---|---|

2 |
11 16 8 4 |