Project Euler #155: Counting Capacitor Circuits.

_{This problem is a programming version of Problem 155 from projecteuler.net}

An electric circuit uses exclusively identical capacitors of the same value .

The capacitors can be connected in series or in parallel to form sub-units, which can then be connected in series or in parallel with other capacitors or other sub-units to form larger sub-units, and so on up to a final circuit.

Using this simple procedure and up to identical capacitors, we can make circuits having a range of different total capacitances. For example, using up to capacitors of each, we can obtain the following distinct total capacitance values:

If we denote by the number of distinct total capacitance values we can obtain when using up to equal-valued capacitors and the simple procedure described above, we have: ...

Find .

Reminder : When connecting capacitors , etc in parallel, the total capacitance is , whereas when connecting them in series, the overall capacitance is given by:

Input Format

Each test file contains a single integer .

Constraints

Output Format

Output a single number i.e.

Sample Input

Sample Output