Transformations#492

Transformations

1 second

64 megabytes

Easy

Let us consider a sequence consisting of a single bit "0". Then, perform $N$ steps as follows: at each step, replace each bit "0" with two bits "10", and each bit "1" with two bits "01".

After the first step, the sequence "0" becomes "10"; after the second step, "0110"; after the third step, "10010110"; after the fourth step, "0110100110010110"; and so on.

Write a program that determines the number of adjacent pairs of bits "00" in the sequence after the $N$ -th step.

Input

The input contains a single integer $N$ ( $1 \leq N \leq 1000$ 1 \leq N \leq 1000).

Output

Print the number of adjacent pairs "00" after the $N$ -th step.

Examples

Example 1

Loading

1 \leq N \leq 1000