{"raw_statement":[{"iden":"problem statement","content":"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:\n\n*   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.\n\nSnuke'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.\nSnuke 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$."},{"iden":"constraints","content":"*   $1 \\leq |S| \\leq 300$\n*   $S$ is a string consisting of `0` and `1`."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$S$"},{"iden":"sample input 1","content":"101"},{"iden":"sample output 1","content":"2\n\nThere are two possible combinations of integers written on the blackboard: ${1,2}$ and ${3}$."},{"iden":"sample input 2","content":"100"},{"iden":"sample output 2","content":"0\n\nThere is no possible combination of integers written on the blackboard."},{"iden":"sample input 3","content":"010101"},{"iden":"sample output 3","content":"3\n\nThere are three possible combinations of integers written on the blackboard: ${2,2,2}$, ${2,4}$, and ${6}$."},{"iden":"sample input 4","content":"11101000111110111101001011110010111110101111110111"},{"iden":"sample output 4","content":"3904"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}