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.

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).

Constraints

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

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

见题面 Input 部分

见题面 Output 部分