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 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 $10000$.

-----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 $1000000009$.

-----Examples-----
Sample Input 1:
1001
Sample Output 1:
3

Sample Input 2:
1111
Sample Output 2:
1

见题面

见题面