Description

给你一堆数：1, 1, 2, 2, 4, 4, ..., 2^k, 2^k（即双份的2的非负整数次幂），再给你一个非负整数n，满足2^k>=n。现将n拆分成这些数中若干个数的和，求拆分方案数。

Format

Input

一个整数n，0<n<10^18

Output

一个整数，即拆分方案数。

Sample 1

Input

10

Output

5

Hint

10 = 8+2 = 8+1+1 = 4+4+2 = 4+4+1+1 = 4+2+2+1+1

Limitation

1s, 512MB for each test case.

Source

Tencent