AT_arc066_b.[ABC050D] Xor Sum

给定一个正整数 $N$。请计算有多少对整数 $u,v$（$0 \leq u, v \leq N$），满足存在非负整数 $a, b$，使得 $a \operatorname{xor} b = u$，$a + b = v$。这里，$\operatorname{xor}$ 表示按位异或运算。由于答案可能非常大，请输出答案对 $10^9+7$ 取模的结果。

输入为一行，包含一个整数 $N$。

输出满足条件的 $u, v$ 的对数，对 $10^9+7$ 取模后的结果。

限制

• $1 \leq N \leq 10^{18}$

样例解释 1

可能的 $u, v$ 对有以下 $5$ 种情况：

• $u=0, v=0$（取 $a=0, b=0$，则 $0 \operatorname{xor} 0=0$，$0+0=0$）
• $u=0, v=2$（取 $a=1, b=1$，则 $1 \operatorname{xor} 1=0$，$1+1=2$）
• $u=1, v=1$（取 $a=1, b=0$，则 $1 \operatorname{xor} 0=1$，$1+0=1$）
• $u=2, v=2$（取 $a=2, b=0$，则 $2 \operatorname{xor} 0=2$，$2+0=2$）
• $u=3, v=3$（取 $a=3, b=0$，则 $3 \operatorname{xor} 0=3$，$3+0=3$）

由 ChatGPT 4.1 翻译