AT_abc129_e [ABC129E] Sum Equals Xor

[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 $ で割った余りを出力せよ。

### 制約 - $ L $は二進数表記で与えられ、先頭文字は必ず $ 1 $ である - $ 1\ \leq\ L\