# 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 |