分数: 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