Welcome to the Digits Parade

2 secs 1024 MB
DivineJK

問題文


ジェラルドは弟のマイケルから以上以下の整数をもらいましたが、なくしてしまいました。 ジェラルドは、を二進数表記したときの桁和がであったことを覚えています。

として考えられるものの個数を(これは素数です)で割ったあまりを求めてください。

制約


  • (下限を1から0に修正しました)

入力


入力は以下の形式で与えられる。

M R

出力


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

入出力例


入力例1


5 2

出力例1


10

として考えられるものは、個です。

入力例2


2 0

出力例2


1

として考えられるものはのみです。

入力例3


1000000000 500

出力例3


380359458

答えは非常に大きくなることがあります。

提出


Go (1.14)