← 返回题目列表

AtCoder · arc066_b

D. 异或和

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给你一个正整数 N。 查找整数对的数量 u 和 v (0≦u,v≦N) 使得存在两个非负整数 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 和 v 是:

  • 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