/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
正整数 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は二進数表記で与えられ、先頭文字は必ず 1 である
- 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) の 5 つが考えられます。
入力例 2
1111111111111111111
出力例 2
162261460
Score : 500 points
Problem Statement
You are given a positive integer L in base two. How many pairs of non-negative integers (a, b) satisfy the following conditions?
- a + b \leq L
- a + b = a \text{ XOR } b
Since there can be extremely many such pairs, print the count modulo 10^9 + 7.
What is XOR?
The XOR of integers A and B, A \text{ XOR } B, is defined as follows:
- When A \text{ XOR } B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.
For example, 3 \text{ XOR } 5 = 6. (In base two: 011 \text{ XOR } 101 = 110.)
Constraints
- L is given in base two, without leading zeros.
- 1 \leq L < 2^{100\ 001}
Input
Input is given from Standard Input in the following format:
L
Output
Print the number of pairs (a, b) that satisfy the conditions, modulo 10^9 + 7.
Sample Input 1
10
Sample Output 1
5
Five pairs (a, b) satisfy the conditions: (0, 0), (0, 1), (1, 0), (0, 2) and (2, 0).
Sample Input 2
1111111111111111111
Sample Output 2
162261460