\(M\) を \(111111\) で割った余りは \(1\) 円玉で支払うしかないので, この部分は組み合わせの数には影響しない. よって, \(N = \floor{M/111111}\) 円を \(1\) 円玉A (元の \(1\) 円玉で全部払うパターン), \(1\) 円玉B (元の \(111111\) 円玉で払うパターン), \(2 \dots 9\) 円玉の \(10\) 種類の硬貨で支払う組み合わせの数を求める問題となる.

\(i\) 番目の硬貨まで見たときに \(j\) 円を支払う組み合わせの数を \(C(i, j)\) とすると,

\[C(i, j) = \sum_k C(i-1, j-ik)\]

となるので, これを DP で計算する. このままでは間に合わないが, よく見ると

\[C(i, j) = C(i-1, j) + C(i, j-i)\]

となるので, これで間に合う.

クエリは先読みしてその最大の \(M_i\) についてのみ計算すれば, 他の \(M_j\) についても \(M_i\) で計算したときの DP の結果が使える.