Bob needs to make a necklace for Anna!

Bob is planning to use exactly \(N\) beads for the necklace. Each bead will be coloured either red or yellow, and you may assume Bob has enough of each colour to make a full necklace.

How many unique necklaces can Bob make?

Here is how Bob defines the equivalence of two necklaces \(A\) and \(B\):

• Let \(A\) and \(B\) be represented as two sequences of size \(N\) and the \(i\)-th term represents the colour of the \(i\)-th bead. If \(A_i = B_i\) for all \(i\) then the two necklaces are equal.
• Let \(C\) represent the sequence \(A\) rotated by a few terms. If \(C = B\) as defined previously, then the two necklaces are equal.

Input Specification

The first and only line contains \(N\) \((1 \le N \le 28)\), the number of beads.

Output Specification

Output consists of one integer, the number of distinct necklaces that Bob can form.

Sample Input

2

Sample Output

3

Explanation of Output

Three possible necklaces can be formed:

1. Two red beads
2. Two yellow beads
3. One red bead and one yellow bead

Note that changing the order of the third necklace will not form another unique necklace.