题目描述

给定一个正整数 $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

输入

3

输出

5

样例 2

输入

1422

输出

52277

样例 3

输入

1000000000000000000

输出

787014179

说明/提示

限制

• $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 翻译