Tony really likes the number 2. He especially likes powers of 2 (e.g. 4, 8, 16, 32...). After playing around with his beloved powers of 2, he has discovered some special numbers that he has called power-difference numbers. Any positive integer that is a power of 2 away from another power of 2 is a power-difference number. For example, 6 is a power-difference number since it is 2 away from 4. Tony wants to find the number of power-difference numbers up to a certain power of 2, inclusive. Help him out!

Note that you may get a power-difference number either by subtraction or addition.

Input Specification

Input will consist of one integer ~N~ ~(0 \le N \le 10000)~.

Output Specification

Output the number of power-difference numbers up to and including ~2^N~.

Subtasks

Subtask 1 (20%)
~0 \le N \le 30~

Subtask 2 (80%)
~0 \le N \le 10000~

Sample Input

1

Sample Output

2

Explanation

1 is a power difference, as 2^1-2^0=1.
2 is a power difference, as 2^2-2^1=2.
2^1=2, so there are only these two power difference numbers in the range.