Factorial Factor of 2

2 secs 1024 MB
OxOmiso's icon OxOmiso

問題文

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

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

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

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

制約

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

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

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

入力

SS

出力

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

入力例 11

11

出力例 11

1

SS11 ,つまり n=3n=3 です。 3!=63!=6 より,2211 回割り切れるので,1110000000071000000007 で割った余りである 11 を出力します。

入力例 22

101100011111000000001111111111111

出力例 22

970599879

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

提出


Go (1.21)