← 返回题目列表

AtCoder · abc129_e

E. 总和等于异或

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

分数: 500 点

问题陈述

给你一个正整数 L 在基地二。 多少对非负整数 (a, b) 满足以下条件?

  • a + b \leq L
  • a + b = a \text{ XOR } b

由于这样的对可能非常多,因此打印计数模数 10^9 + 7.

什么是异或?

整数的异或 A 和 B, A \text{ XOR } B,定义如下:

  • 当 A \text{ XOR } B 以基数 2 书写,即 2^k的地点 (k \geq 0)是 1 如果 A or B,但不是两者都有 1 在 2^k的地点,以及 0 否则。

例如, 3 \text{ XOR } 5 = 6。 (在基数二中: 011 \text{ XOR } 101 = 110.)

约束

  • L 以基数 2 给出,没有前导零。
  • 1 \leq L < 2^{100\ 001}

输入

输入由标准输入按以下格式给出:

L

输出

打印对数 (a, b) 满足条件,取模 10^9 + 7.


示例输入 1

10

示例输出 1

5

五对 (a, b) 满足条件: (0, 0), (0, 1), (1, 0), (0, 2) 和 (2, 0).


示例输入 2

1111111111111111111

示例输出 2

162261460