Counting Bus Transfer Plans on the Ring Road

In the newly built ring road of Changsha City there are 8 bus stops labeled \(A, B, C, D, E, F, G, H\) arranged consecutively on a circle. Buses can only travel between two adjacent stops. For example, going from stop \(A\) to stop \(D\) requires at least 3 transfers (i.e. riding from \(A \to B\), \(B \to C\), and \(C \to D\)).

It is known that one can go from stop \(A\) to stop \(E\) with just 4 transfers (either along the path \(A \to B \to C \to D \to E\) or the other way round \(A \to H \to G \to F \to E\)). However, Tiger, who has a terrible sense of direction, ended up making a total of \(n\) transfers before arriving at \(E\) (note that once Tiger reaches \(E\), he will not continue transferring).

Your task is to calculate the number of possible riding plans that Tiger could have taken, i.e. the number of different paths from \(A\) to \(E\) using exactly \(n\) transfers, under the condition that the bus will never go to \(E\) before the final transfer.

Note: The stops are arranged in a circle. At every intermediate step (before the final step), if a transfer would lead to stop \(E\), that move is not allowed.

inputFormat

The input consists of a single integer \(n\) \((n \ge 0)\) representing the total number of transfers Tiger made.

Note: If \(n < 4\), it is impossible to reach \(E\) from \(A\) without arriving at \(E\) prematurely. In such cases, the answer is 0.

outputFormat

Output a single integer representing the number of possible riding plans.

sample

4

2