As you might know, the memory in current computers
consists of a sequence of bits and each of these bits can be in
two possible states. Megan’s company has now developed a great
new memory unit where every bit has three possible states. This
would all be great, if it wasn’t for Megan’s boss. The boss
wants her to write a program for this memory unit for integer
operations, but instead of using ternary base (i.e., base 3),
Megan’s boss decided that the bits should be interpreted as a
binary number, with the exception that the digit 2 is allowed
as well.
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 nonnegative 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
