A telecom channel-allocation scheme forbids two consecutive 1 bits anywhere in a code's binary representation (to avoid electromagnetic interference between adjacent channels). A positive integer is called interference-free if its binary representation contains no two adjacent 1 bits.
Given N, count how many integers in [1, N] are interference-free.
Input format
Line 1: a single integer N.
Output format
A single integer: the count of interference-free integers in [1, N].
Constraints
- 1 ≤ N ≤ 1,000,000,000,000,000,000