题目描述

给定一个正整数 $N$，找到满足以下条件的整数对 $u$ 和 $v$ 的数量：存在两个非负整数 $a$ 和 $b$，使得 $a$ $xor$ $b=u$ 且 $a+b=v$。这里，$xor$ 表示按位异或。由于可能非常大，请计算答案模 $10^9+7$。

约束条件

• $1≦N≦10^{18}$

输入

输入以以下格式从标准输入给出：

$N$

输出

打印可能整数对 $u$ 和 $v$ 的数量，以 $10^9+7$ 取模。

示例输入 1

3

示例输出 1

5

满足条件的五个整数对为：

• $u=0,v=0$ （取 $a=0,b=0$，则 $0$ $xor$ $0=0$，$0+0=0$）。

• $u=0,v=2$ （取 $a=1,b=1$，则 $1$ $xor$ $1=0$，$1+1=2$）。

• $u=1,v=1$ （取 $a=1,b=0$，则 $1$ $xor$ $0=1$，$1+0=1$）。

• $u=2,v=2$ （取 $a=2,b=0$，则 $2$ $xor$ $0=2$，$2+0=2$）。

• $u=3,v=3$ （取 $a=3,b=0$，则 $3$ $xor$ $0=3$，$3+0=3$）。

示例输入 2

1422

示例输出 2

52277

示例输入 3

1000000000000000000

示例输出 3

787014179