The Time‐Space Door Challenge

As the chimes of \(2024\) echo through the kingdom, the legendary time–space door opens once again. This mysterious portal connects two mystical numeric realms: the binary realm and the quaternary (base-4) realm.

In the binary realm, a hero’s power is measured by the sum of the digits in the binary representation of his strength value, i.e. if \(n\) is expressed in base \(2\) then his power is \(S_2(n)\) (which is the number of 1’s in \(n\)).

In the quaternary realm, his power is similarly defined as the sum of the digits when \(n\) is written in base \(4\), i.e. \(S_4(n)\). A hero can cross the time–space door if and only if \(S_2(n)=S_4(n)\). It turns out that this condition is equivalent to the number \(n\) having a base-4 representation containing only the digits 0 and 1. In other words, \(n\) must be expressible as a sum of distinct powers of 4.

The king has assembled heroes with strength values from \(1\) to \(N\) (in the legend \(N=2024\), but in this problem \(N\) is given as input). As the chosen guide, your task is to help count how many heroes satisfy the condition and can therefore pass through the time–space door.

Note: A positive integer \(n\) satisfies the condition if and only if it can be written in the form \[ n=\sum_{i\in I}4^i, \] where \(I\) is a nonempty subset of nonnegative integers and the sum does not exceed \(N\).

inputFormat

The input consists of a single integer \(N\) (\(1\leq N\leq 10^4\)).

For example, if \(N=2024\) then the heroes have strength values from 1 to 2024.

outputFormat

Output a single integer representing the number of heroes among \(1\) to \(N\) that satisfy \(S_2(n)=S_4(n)\), i.e. the number of valid numbers \(n\) that can be expressed as a sum of distinct powers of 4 and \(n\leq N\).

sample

1

1