Factorial Factor of 2

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

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

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

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

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

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

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

11

1

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

101100011111000000001111111111111

970599879

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