CF750G.New Year and Binary Tree Paths

The New Year tree is an infinite perfect binary tree rooted in the node 1. Each node v has two children: nodes indexed (2·v) and (2·v + 1).

Polar bears love decorating the New Year tree and Limak is no exception. As he is only a little bear, he was told to decorate only one simple path between some pair of nodes. Though he was given an opportunity to pick the pair himself! Now he wants to know the number of unordered pairs of indices (u, v) (u ≤ v), such that the sum of indices of all nodes along the simple path between u and v (including endpoints) is equal to s. Can you help him and count this value?

新年树是一棵以节点 1 为根的无限完全二叉树。每个节点 $v$ 都有两个子节点：编号分别为 $(2\cdot v)$ 和 $(2\cdot v + 1)$ 的节点。

北极熊们热衷于装饰新年树，小熊 Limak 也不例外。由于他尚年幼，被要求仅装饰某一对节点之间的唯一简单路径。不过，他被允许自行选择这对节点！现在，他想知道满足如下条件的无序节点对 $(u,\,v)$（其中 $u \le v$）的个数：该节点对之间简单路径上所有节点（含端点）的编号之和恰好等于 $s$。你能帮他计算出这个数值吗？

The only line of the input contains a single integer s (1 ≤ s ≤ 1015).

输入仅包含一行，其中有一个整数 $s$（$1 \leq s \leq 10^{15}$）。

Print one integer, denoting the number of unordered pairs of nodes indices defining simple paths with the sum of indices of vertices equal to s.

输出一个整数，表示满足以下条件的无序节点索引对的数量：该节点对定义了一条简单路径，且路径上所有顶点的索引之和等于 $s$。

In sample test, there are 4 paths with the sum of indices equal to 10:

在样例测试中，有 4 条路径的下标之和等于 10：