Problem I
Increasing and Decreasing alternately sequences
Time Limit:3000MS Memory Limit:50000K
Description
There are some particular sequences with the following property:
(1) The first term is 1;
(2) Every term of the sequences is 1, 2 or 3;
(3) The terms are changed alternately. That is, for neighboring three terms x1, x2,x3, x1<x2>x3 or
x1>x2<x3.
For example, there are only 3 particular sequences of length 3: 121, 132, 131. Now your job is to
calculate the number an of particular sequences of length n.
Input
The input will consist of several rows. There is number n on each row, which is the length of particular
sequences, 1<=N<=63.
Output
The output will consist of one line for each line of input giving the exact value of an.
Sample Input
37
Sample Output
3
21