配点 : $500$ 点

問題文

正整数 $L$ が二進数表記で与えられます。 以下の条件を満たす非負整数 $a, b$ の組 $(a, b)$ がいくつ存在するか求めてください:

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

ただし、この値は非常に大きくなることがあるので、$10^9 + 7$ で割った余りを出力してください。

制約

• $L$は二進数表記で与えられ、先頭文字は必ず $1$ である
• $1 \leq L < 2^{100,001}$

入力

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

$L$

出力

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

10

5

条件を満たす $(a, b)$ としては $(0, 0), (0, 1), (1, 0), (0, 2), (2, 0)$ の $5$ つが考えられます。

1111111111111111111

162261460