Water Treatment Plants

River pollution control is a major challenge for authorities that must ensure a clean future water supply. Sewage treatment plants clean up the dirty water coming from cities before it is discharged into the river.

As part of a coordinated plan, a pipeline connects the cities to the sewage treatment plants distributed along the river. It is more efficient to run some treatment plants at full capacity and switch the less-used ones off for a while. So each city has its own treatment plant by the river, plus a pipe to its neighbouring city upstream and a pipe to the next city downstream. At each city's plant there are three choices:

• process the water it receives from one neighbouring city, together with its own dirty water, and discharge the cleaned water into the river;
• send its own dirty water, plus any from its downstream neighbour, to the upstream neighbouring city's plant (provided that city is not already using the pipe to send its own water downstream);
• send its own dirty water, plus any from its upstream neighbour, to the downstream neighbouring city's plant, if that pipe is not being used.

These choices guarantee that:

• every city has its water treated somewhere, and
• at least one city discharges cleaned water into the river.

Represent a city that discharges water into the river as V (a downward flow), a city that passes its water to the neighbour on its right as >, and a city that passes its water to the neighbour on its left as <. With several cities along the bank, assign one symbol to each city and list the symbols in order. For example, two cities A and B can:

• each treat their own sewage and discharge clean water, so both act as V and we write VV;
• or A can send its sewage to the right, to B, for treatment and discharge, written >V;
• or B can send its sewage to the left, to A, which treats it together with its own water and discharges it, written V<.

We cannot have ><, because that means A sends its water to B while B sends its water to A, so both use the same pipe, which is not allowed. Likewise the leftmost city cannot be <, because there is no city further to its left to receive the water.

So there are exactly 3 valid set-ups for two cities:

         A    B       A > B       A < B
         V    V           V       V
  RIVER~ ~ ~ ~ ~     ~ ~ ~ ~ ~   ~ ~ ~ ~ ~RIVER
          "VV"        ">V"         "V<"

For three cities there are 8 possible set-ups.

Given the number of cities NC (equal to the number of treatment plants) along the river bank, determine NS, the number of possible set-ups that obey the rules above. Note that NC can be as large as 100.

The input is a sequence of values, one per line. Each value is a number of cities NC. Read values until the end of input.

For each value in the input, output a single line containing NS, the number of possible set-ups for that number of cities, in the same order as the input.