The Garland#77
A New Year tree is decorated with a garland of infinite length, consisting of bulbs connected in sequence.
When the garland is switched on, only the first bulb (the one closest to the switch) lights up and stays lit for one second. Afterwards, the bulbs on the garland start blinking according to the following rule:
At each second, for every bulb, if exactly one of its adjacent bulbs is lit, then this bulb will be lit in the next second; otherwise, it will not be lit. The first bulb has only one neighbor.
Write a program that, given an integer , determines how many bulbs will be lit at the -th second.
One integer (1 \leq n \leq 10^9) — the number of the second.
Output a single integer — the number of bulbs that will be lit at the -th second.
Example 1