[ABC129E] Sum Equals Xor

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

[problemUrl]: https://atcoder.jp/contests/abc129/tasks/abc129_e 正整数 $ L $ が二進数表記で与えられます。 以下の条件を満たす非負整数 $ a,\ b $ の組 $ (a,\ b) $ がいくつ存在するか求めてください: - $ a\ +\ b\ \leq\ L $ - $ a\ +\ b\ =\ a\ \text{\ XOR\ }\ b $ ただし、この値は非常に大きくなることがあるので、$ 10^9\ +\ 7 $ で割った余りを出力してください。 XOR とは 整数 $ A,\ B $ のビットごとの排他的論理和 $ a\ \text{\ XOR\ }\ b $ は、以下のように定義されます。 $ a\ \text{\ XOR\ }\ b $ を二進数表記した際の $ 2^k $ ($ k\ \geq\ 0 $) の位の数は、$ A,\ B $ を二進数表記した際の $ 2^k $ の位の数のうち一方のみが $ 1 $ であれば $ 1 $、そうでなければ $ 0 $ である。 例えば、$ 3\ \text{\ XOR\ }\ 5\ =\ 6 $ となります (二進数表記すると: $ 011\ \text{\ XOR\ }\ 101\ =\ 110 $)。

入力は以下の形式で標準入力から与えられる。 > $ L $

条件を満たす組 $ (a,\ b) $ の個数を $ 10^9\ +\ 7 $ で割った余りを出力せよ。

10

5

1111111111111111111

162261460

### 制約 - $ L $は二進数表記で与えられ、先頭文字は必ず $ 1 $ である - $ 1\ \leq\ L\ <\ 2^{100,001} $ ### Sample Explanation 1 条件を満たす $ (a,\ b) $ としては $ (0,\ 0),\ (0,\ 1),\ (1,\ 0),\ (0,\ 2),\ (2,\ 0) $ の $ 5 $ つが考えられます。