Problem D
Pavers

J. Pierpont Flathead, Dauntless Banker and Financier. Source: The Zork Library

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.

1

2 2 1 0

2

11 16 8 4