{"problem":{"name":"01 Record","description":{"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:","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc048_f"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $1 \\leq |S| \\leq 300$\n*   $S$ is a string consisting of `0` and `1`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc048_f","tags":[],"sample_group":[["101","2\n\nThere are two possible combinations of integers written on the blackboard: ${1,2}$ and ${3}$."],["100","0\n\nThere is no possible combination of integers written on the blackboard."],["010101","3\n\nThere are three possible combinations of integers written on the blackboard: ${2,2,2}$, ${2,4}$, and ${6}$."],["11101000111110111101001011110010111110101111110111","3904"]],"created_at":"2026-03-03 11:01:14"}}