桁DPを使う.

何桁目まで見たか, 最大値かどうか, \(D\) で割った余りをキーにして総数を値として桁DPを行う.

計算量は \(O(D \log K)\) である.