题目描述

给出正整数$N$.

求出整数对$u$和$v$ $(0≤u,v≤N)$的数目，使得存在两个非负整数$a$和$b$满足$a\ xor\ b = u$和$a\ +\ b= v$。这里，$xor$表示按位异或。 要求对答案取模$10^9 + 7$。

输入输出格式

输入格式

一个正整数$N$

输出格式

满足条件的$u,v$的个数，对$10^9+7$取模

数据范围：

$N<=10^{18}$