Problem E
Three-State Memory
For example, $201$ in this strange representation is $2\cdot 2^2+0\cdot 2^1+ 1\cdot 2^0=9$. Some numbers are shorter in this representation, but for other numbers it doesn’t help at all – for instance, $15$ is $1111$ in binary and this is the only way of writing it in the new representation as well.
It seems that there is nothing else that Megan can do to convince her boss. Since she likes math, she started wondering about different representations of the same number. For example 9 has three representations: $201, 121$ and $1001$. Can you help her figure out how many representations a given number has?
Input
The first and only line of the input contains a string consisting of ’0’ and ’1’. The string represents a non-negative integer $N$ in binary. The leftmost bit is the most significant one. The number of bits will be at least $1$ and at most $10\, 000$.
Output
Output a line giving the number of different binary representations of $N$ that also use $2$ as a digit. Since this number might be big, output the remainder modulo $1\, 000\, 000\, 009$.
| Sample Input 1 | Sample Output 1 |
|---|---|
1001 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
1111 |
1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
00000 |
1 |
