← 返回题目列表

Codeforces · 750/G

G. 新年和二叉树路径

中文机器翻译题面 查看原题

新年树是一个以节点 1 为根的无限完美二叉树。每个节点 v 有两个子节点:索引为 (2·v) 和 (2·v + 1) 的节点。

北极熊喜欢装饰新年树,利马克也不例外。由于他只是一只小熊,因此他被告知只能在一对节点之间装饰一条简单的路径。尽管他有机会亲自挑选这双鞋!现在他想知道无序索引对 (u, v) (u ≤ v) 的数量,使得 u 和 v 之间的简单路径(包括端点)上的所有节点的索引之和等于 s。你能帮他算一下这个值吗?

输入

输入的唯一行包含单个整数 s (1 ≤ s ≤ 1015)。

输出

打印一个整数,表示定义简单路径且顶点索引之和等于 s 的无序节点索引对的数量。

示例

输入 #1

10

输出 #1

4

注意

样本测试中,索引总和等于10的路径有4条: