Count Popcount

2 secs 1024 MB
sten's icon sten

問題文

整数 N,MN, M が与えられます。

f(x)=f(x) = xx22 進法での各桁の和
としたとき、00 以上 NN 以下の整数 xx であって f(x)=Mf(x) = M であるような xx の個数を求めてください。

制約

  • 0N<10180 \leq N < 10^{18}
  • 0M<640 \leq M < 64

入力

N M

出力

答えを出力してください。

サンプル

入力1
4 2
出力1
1

f(0)=0,f(1)=1,f(2)=1,f(3)=2,f(4)=1f(0) = 0, f(1) = 1, f(2) = 1, f(3) = 2, f(4) = 1 であるため、f(x)=2f(x) = 2 を満たす xx33 のみです。


入力2
19 3
出力2
5

提出


Go (1.21)