Factorial Factor of 2

2 secs 1024 MB
OxOmiso

問題文


正の整数 が, 進法表記で として与えられます。

で何回割りきれるでしょうか?

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

なお, は, から までの全ての正の整数の積を表します。

制約


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

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

入力


出力


で何回割り切れるかを, で割った余りを出力してください。 出力後の改行も行ってください。

入力例


11

出力例


1

11 ,つまり です。 より, 回割り切れるので, で割った余りである を出力します。

入力例


101100011111000000001111111111111

出力例


970599879

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

提出


Go (1.14)