405705: GYM102051 F Nate and Fan Meet-and-Greet

Nate is attending a meet-and-greet for his favorite celebrity voice actress, Hana Kanazawa! You might know her from her voice-over work in the Mono Guitar Hero series, Doreimon, its sequel Durararaemon, and of course, Angel Beats Agents. She announced that she would give a signed copy of her new album to whomever could guess the serial number on Volume $$$x$$$ of her favorite manga.

Nate, of course, knows that this would be the volume of The World Dog Only Knows that introduces the character Shiori, whom she voices in the anime. He also happens to know that for this series, the serial number of Volume $$$n$$$, $$$s_n$$$, satisfies the following:

• The pilot, Volume $$$0$$$, has a serial number of $$$0$$$.
• The very first volume, Volume $$$1$$$, has a serial number of $$$1$$$.
• The serial number of every volume after the first is calculated as $$$s_n = 2 s_{n-1} - s_{n-2}$$$.

Here, $$$s_{n-1}$$$ is the serial number of Volume $$$n-1$$$ and $$$s_{n-2}$$$ is the serial number of Volume $$$n-2$$$.

Nate can't think well under pressure, and a signed album from his favorite celebrity is in jeopardy! Can you help him find the serial number of Volume $$$x$$$?

The input consists of a line with only a single integer $$$x$$$, the volume whose serial number must be found.

Constraints

$$$1 \le x \le 10^{18}$$$

Output a single integer, the serial number of Volume $$$x$$$.

1

1

2

2

The serial number of Volume $$$1$$$ is given from the definition. The serial number of Volume $$$2$$$ is $$$2s_1-s_0=2$$$.