题目描述

以二进制形式给出一个整数 $L$，问有多少个非负整数对 $(a, b)$ 满足：$a+b = a \oplus b \le L$。答案对 $10^9 + 7$ 取模。

输入格式

一个二进制数 $L$，$1 \le L < 2^{100001}$。

输出格式

满足条件的非负整数对 $(a, b)$ 的个数。

10

5

1111111111111111111

162261460