There are more games?? How ridiculous!

In front of you lies a glass bridge with ~N~ (~1 \leq N \leq 10^{18}~) panels. These panels are designed to hold piles of cookies, of course.

Initially, there is one cookie on panel ~1~. The Front Man proceeds to apply the following operation to the panels, sequentially, with ~i~ from ~1~ to ~N~:

For each cookie on panel ~i~, add a cookie to panels ~2i~, ~2i + 1~, and ~3i~.

The Front Man then asks you a simple question: How many cookies are on panel ~N~?

Input Specification

The first line contains the integer ~N~ (~1 \leq N \leq 10^{18}~).

Output Specification

Output one line containg the number of cookies on panel ~N~.

Subtasks

Subtask 1 [20%]

~1 \leq N \leq 10^6~

Subtask 2 [80%]

No additional constraints.

Sample Input 1

3

Sample Output 1

2

Sample Explanation 1

The number of cookies on the panels are [~1, 1, 2~].

When applying the operation to panel ~1~, one cookie is added to each of panels ~2~, ~3~, and ~3~.

When applying the operation to panel ~2~, one cookie is added to each of panels ~4~, ~5~, and ~6~. This has no effect on panel ~3~.

When applying the operation to panel ~3~, two cookies are added to each of panels ~6~, ~7~, and ~9~. This has no effect on panel ~3~.

Therefore, the number of cookies on panel ~3~ is ~2~ after all the operations have been applied.

Sample Input 2

999999999999999999

Sample Output 2

6893394