E - Sum Equals Xor

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500

問題文

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

  • a + b \leq L
  • a + b = a \mbox{ XOR } b

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

XOR とは

整数 A, B のビットごとの排他的論理和 a \mbox{ XOR } b は、以下のように定義されます。

a \mbox{ XOR } b を二進数表記した際の 2^k (k \geq 0) の位の数は、A, B を二進数表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。 例えば、3 \mbox{ XOR } 5 = 6 となります (二進数表記すると: 011 \mbox{ 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 \mbox{ 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 \mbox{ XOR } B, is defined as follows:

  • When A \mbox{ 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 \mbox{ XOR } 5 = 6. (In base two: 011 \mbox{ 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