Uncle Shiva has gifted Nikhil a new toy. Uncle Shiva believes in gifting toys with a mathematical flavour and this is no different. This toy consists of a wooden board with wooden pegs. The pegs are arranged in N columns with 3 pegs in each column. Each peg is coloured Red, Blue or Green.

Nikhil has a set of N − 1 elastic bands (i.e. rubber bands). He builds a chain of bands linking column 1 to column N as follows. He starts by placing a band from a peg in column 1 to a peg in column 2. From the peg where the first band ends, he places a second band connecting that peg in column 2 to a peg in column 3. Continuing in this way, he places all N − 1 bands to connect the N columns.

While building this chain of elastic bands, he is not allowed to connect two pegs at the same position in adjacent columns. So for instance, the second peg on column i cannot be connected to the second peg on column i − 1 or the second peg on column i + 1. It may be connected to any other peg in those two neighbouring columns.

Uncle Shiva has added a constraint. Nikhil has to arrange the bands so that while moving from column 1 to column N along the bands, the number of red pegs encountered should be even (i.e. 0 or 2 or 4 or . . .).

Nikhil is way too smart for Uncle Shiva and he can solve this game in a jiffy. Instead, he decides to count the number of ways in which he can solve the game.

Your task is to compute the number of solutions for some of the given arrangements of pegs.

The full task can be found in this PDF file: http://www.iarcs.org.in/inoi/2016/zio2016/zio2016-question-paper.pdf

Would appreciate any help people can provide in solving this problem. Thanks