You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

大明和新新今天学习了“按位异或”这种运算。 异或_百度百科 (baidu.com)

题目描述

给你一个正整数 $n$，请你求出有多少个有序数对 $(x,y)$ 满足：

• $0≤x≤n$
• $0≤y≤n$
• $x+y=x⊕y$

其中 $⊕$ 是异或运算。答案对 $1e9+7$ 取模。

数据格式

输入格式

一个正整数 $n$

输出格式

一个数字表示答案。答案对 $1e9+7$ 取模。

样例

3

9

149

3867

40789

27081051

1004863

449860530

40130924559

915012752

数据范围

• 样例1解释：
• $n=3$
• $(0,0)$
• $(0,1)$
• $(0,2)$
• $(0,3)$
• $(1,0)$
• $(1,2)$
• $(2,0)$
• $(2,1)$
• $(3,0)$
• 对于10%的数据，保证 $0≤n≤10^9$
• 对于100%的数据，保证 $0≤n≤10^{1000}$
• 啥？你问我需不需要高精度？当然需要一点喽！还要注意时空限制哦！