問題文

正の整数 $n$ が，$2$ 進法表記で $S$ として与えられます。

$n!$ は $2$ で何回割りきれるでしょうか？

答えはとても大きくなる可能性があるので，答えを $1000000007$ で割った余りを求めてください。

なお，$n!$ は，$1$ から $n$ までの全ての正の整数の積を表します。

制約

• $1\leq|S|\leq10^5$

• $S$ の各文字は 0 または 1 である。

• $S$ の上から $1$ 桁目は $1$ である。

入力

出力

$n$ が $2$ で何回割り切れるかを，$1000000007$ で割った余りを出力してください。 出力後の改行も行ってください。

入力例 $1$

11

出力例 $1$

1

$S$ が 11 ，つまり $n=3$ です。 $3!=6$ より，$2$ で $1$ 回割り切れるので，$1$ を $1000000007$ で割った余りである $1$ を出力します。

入力例 $2$

101100011111000000001111111111111

出力例 $2$

970599879

$n=5970599935$ です。答えはとても大きくなることがあるので，$1000000007$ で割った余りを求めてください。