F - 01 Record Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 2200 点

問題文

すぬけくんは大きな黒板をもらいました． これに喜んだすぬけくんは，まず，黒板にいくつかの正整数を書きました． 次にすぬけくんは，黒板に書かれている整数がなくなるまで，以下の操作を繰り返し行いました．

  • 黒板に書かれている整数を 1 つ選び，消す． 消した整数を x とする． 次に，x を 2 で割ったあまりをノートに記録する． 最後に，x \geq 2 である場合は，新たに x-1 を黒板に書き加える．

すぬけくんの記録は，0 と 1 からなる文字列 S によって表されます． これは，すぬけくんが i 回目の操作で選んだ整数を 2 で割ったあまりが S_i であることを表します．

すぬけくんは，最初に黒板に書いた正整数の組み合わせを忘れてしまいました． 文字列 S の情報から，最初に黒板に書いた正整数の組み合わせとしてありうるものが何通りあるか求めてください． ここで，正整数の組み合わせ a と b が異なるとは，ある整数 v が存在して，a に含まれる v の個数と b に含まれる v の個数が異なることを意味します． なお，答えは非常に大きくなることがあるので，10^9+7 で割ったあまりを求めてください． また，すぬけくんの記録が間違っており，条件を満たす正整数の組み合わせが存在しないこともありますが，その場合は単に 0 と答えてください．

制約

  • 1 \leq |S| \leq 300
  • S は 0 と 1 からなる文字列．

入力

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

S

出力

最初に黒板に書いた正整数の組み合わせとしてありうるものの数を 10^9+7 で割ったあまりを出力せよ．

入力例 1

101

出力例 1

2

最初に黒板に書いた整数の組み合わせとしてあり得るのは，\{1,2\},\ \{3\} の 2 つです．

入力例 2

100

出力例 2

0

最初に黒板に書いた整数の組み合わせとしてあり得るものはありません．

入力例 3

010101

出力例 3

3

最初に黒板に書いた整数の組み合わせとしてあり得るのは，\{2,2,2\},\ \{2,4\},\ \{6\} の 3 つです．

入力例 4

11101000111110111101001011110010111110101111110111

出力例 4

3904

Score : 2200 points

Problem Statement

Snuke received a big blackboard. Being pleased with this present, he first wrote some positive integers. Then, he repeated the following operation until there was no integer written on the blackboard:

  • Choose one integer written on the blackboard and erase it. Let x be the erased integer. Then, record the remainder of x divided by 2 on his notebook. Finally, if x \geq 2, write a new integer x-1 on the blackboard.

Snuke's record is represented by a string S consisting of 0 and 1, where S_i is the remainder of the chosen integer divided by 2 in the i-th operation.

Snuke forgot the combination of positive integers he first wrote on the blackboard. From the information given as the string S, find the number of possible combinations of positive integers he first wrote on the blackboard. Here, we consider combinations a and b of positive integers different when there is an integer v such that the numbers of times v occurs in a and v occurs in b differ. Since the count can be enormous, compute it modulo (10^9+7). Also, it is possible that Snuke's record is incorrect and that no combination of positive integers satisfies the condition. In such a case, just answer 0.

Constraints

  • 1 \leq |S| \leq 300
  • S is a string consisting of 0 and 1.

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of possible combinations of positive integers written on the blackboard, modulo (10^9+7).

Sample Input 1

101

Sample Output 1

2

There are two possible combinations of integers written on the blackboard: \{1,2\} and \{3\}.

Sample Input 2

100

Sample Output 2

0

There is no possible combination of integers written on the blackboard.

Sample Input 3

010101

Sample Output 3

3

There are three possible combinations of integers written on the blackboard: \{2,2,2\}, \{2,4\}, and \{6\}.

Sample Input 4

11101000111110111101001011110010111110101111110111

Sample Output 4

3904