A digital art collective starts every new piece as a single square canvas panel. Whenever they choose to subdivide, every existing panel on the canvas is simultaneously split into exactly four equal quarter-panels, so after k whole subdivision rounds (k >= 0) a canvas that started as one panel now has exactly 4^k panels in total. Given the number of panels currently on a canvas, determine whether that count could have arisen from starting at one panel and applying this quadrupling subdivision some whole number of times (zero or more).

Input format

A single line containing one integer n.

Output format

Print true if n panels could result from applying the quadrupling subdivision to a single starting panel zero or more whole times (that is, n equals 4 raised to some non-negative integer power), and false otherwise.

Constraints

• -2^31 <= n <= 2^31 - 1

16

true

5

false