Military parade P35187

Statement

Usually, each group of soldiers in a military parade stands in three columns, all equally long. But what happens if $n$ , the number of soldiers, is not a multiple of 3? Is such a group acceptable? And, if so, how must the soldiers stand?

To solve this question, consider the following set of rules for every $n$ (multiple of 3 or not):

There must be exactly three columns of soldiers.
The first row must have exactly three soldiers.
The last row must have exactly three soldiers.
The whole group of soldiers must be connected. Here, we assume that two soldiers are directly connected if one stands to the right, left, in front, or back of the other. Note that we do not consider diagonal connections.

Below you can see four of the 41174 valid ways to place 18 soldiers in a parade. Beware: the soldiers are facing to the left side, so columns are rows, and rows are columns! The first is the traditional way.

(50,2)

(1,0)0.400(1,0) (1,1)0.401(1,1) (1,2)0.402(1,2) (2,0)0.403(2,0) (2,1)0.404(2,1) (2,2)0.405(2,2) (3,0)0.406(3,0) (3,1)0.407(3,1) (3,2)0.408(3,2) (4,0)0.409(4,0) (4,1)0.410(4,1) (4,2)0.411(4,2) (5,0)0.412(5,0) (5,1)0.413(5,1) (5,2)0.414(5,2) (6,0)0.460(6,0) (6,1)0.461(6,1) (6,2)0.462(6,2)

(9,0)0.415(9,0) (9,1)0.416(9,1) (9,2)0.417(9,2) (10,0)0.418(10,0) (11,0)0.419(11,0) (12,0)0.420(12,0) (13,0)0.421(13,0) (14,0)0.422(14,0) (15,0)0.423(15,0) (16,0)0.424(16,0) (17,0)0.425(17,0) (18,0)0.426(18,0) (19,0)0.463(19,0) (20,0)0.464(20,0) (21,0)0.465(21,0) (22,0)0.427(22,0) (22,1)0.428(22,1) (22,2)0.429(22,2)

(25,0)0.430(25,0) (25,1)0.431(25,1) (25,2)0.432(25,2) (26,0)0.433(26,0) (26,2)0.434(26,2) (27,0)0.435(27,0) (27,1)0.436(27,1) (27,2)0.437(27,2) (28,1)0.466(28,1) (28,2)0.438(28,2) (29,2)0.439(29,2) (30,1)0.440(30,1) (30,2)0.467(30,2) (31,0)0.468(31,0) (31,2)0.441(31,2) (32,0)0.442(32,0) (32,1)0.443(32,1) (32,2)0.444(32,2)

(35,0)0.445(35,0) (35,1)0.446(35,1) (35,2)0.447(35,2) (36,1)0.469(36,1) (37,1)0.470(37,1) (37,2)0.471(37,2) (38,2)0.448(38,2) (39,0)0.449(39,0) (39,2)0.450(39,2) (40,0)0.451(40,0) (40,1)0.452(40,1) (40,2)0.453(40,2) (41,0)0.454(41,0) (41,2)0.455(41,2) (42,2)0.456(42,2) (43,0)0.457(43,0) (43,1)0.458(43,1) (43,2)0.459(43,2)

Using the rules above, for (almost) every $n$ , any group of $n$ soldiers can participate in a military parade. But now we face another problem: in general, there are too many ways to place the soldiers. Can you count this number?

Input

Input consists of several natural numbers $n$ between 1 and 50. A special case with $n = 0$ ends the input.

Output

For every $n$ , print $n$ and the number of ways to place $n$ soldiers in a parade. This number will never be larger than $10^{18}$ .

Public test cases

Input

Output

5 : 0
6 : 1
7 : 3
8 : 6
9 : 16
18 : 41174
40 : 9295604587740

Information

Author: Salvador Roura
Language: English
Official solutions: C++
User solutions: C++