Simple Nine Rings Puzzle

Given a binary string $s$ (the rule string) and a state string $t$ of length $|s|+1$, we consider the following puzzle. In the state string $t$, each character represents a ring: $t_i = \texttt{1}$ means the $i$-th ring is assembled while $t_i = \texttt{0}$ means it is taken apart. Initially, all rings are taken apart (i.e. $t=\texttt{0}^{|s|+1}$) and the goal is to get all rings assembled (i.e. $t=\texttt{1}^{|s|+1}$).

In each move, you may toggle (i.e. change a $0$ to $1$ or a $1$ to $0$) exactly one character $t_i$ of $t$, but only if the prefix of $t$ before that position, namely $t_1t_2\cdots t_{i-1}$, is a suffix of the rule string $s$. (Note that the empty string is considered a suffix of any string, so the first ring can always be toggled.)

For example, if $s=\texttt{01}$ then its suffixes are ({"", \texttt{1}, \texttt{01}}). In a state such as $t=\texttt{010}$ of length 3, the move at position 3 is allowed only if the prefix $t_1t_2=\texttt{01}$ is a suffix of $s$.

Your task is to compute the minimum number of moves required to change $t$ from all zeros to all ones, and output the answer modulo $10^9+7$.

inputFormat

A single line containing the binary string $s$. It is guaranteed that $s$ consists only of characters 0 and 1.

outputFormat

Output a single integer --- the minimum number of moves required to change the state from all zeros to all ones modulo $10^9+7$.

sample

1

2