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