T1
题目大意：
给出 \(n,P\)，问有多少个不含 \(0\) 的 \(n\) 位正整数满足数位上的数字从左到右不降且是 \(P\) 的倍数（\(n\le 10^{18},P\le 500\)）。
由于要求不降，可以发现至多只有 \(8\) 个交界处，除交界处以外全为一个数字。
重新看填数字的过程，可以看作先给全部位设为 \(1\) 然后可以选一个后缀给每个数位加 \(1\)（即设成 \(2\)，再加 \(1\) 就是设为 \(3\)），这个后缀加 \(1\) 操作可以做 \(8\) 次。
但如果从每一次操作给那个后缀加了的角度考虑，要限定每次选后缀的长度不降以防止算重，这样状态是 \(\mathcal O(np)\) 的。
赛时想法
记 \(h(i)=\dfrac{10^i-1}{9}\) 表示 \(i\) 位后缀的值。
可以设 \(f_{i,j,k}\) 为处理完 \(i\) 次加 \(1\)，值模 \(P\) 为 \(j\)，最后一次选后缀的长度为 \(k\) 的方案数。
转移枚举 \(p=k\sim n\)
\[f_{i+1,(j+h(p))\%P,p}\gets f_{i+1,(j+h(p))\%P,p}+f_{i,j,k}(k\le p)
\]