题目描述

对于数组元素均不大于 $9$ 的正整数数组 $a$，定义数组 $a$ 的价值为将数组元素拼接在一起得到的十进制数，例如数组 $a=\{1,1,4,5,1,4\}$ 的价值 $val_{a}=114514$ .

给定正整数 $n,m\ (1\le m\le 9)$，求长度为 $n$ 且所有元素均不大于 $m$ 的所有非严格单调递增的正整数数组的价值和，答案对 $10^9+7$ 取模.

数据范围

$①$ $1\le n\le 10^6$

$②$ $1\le n\le 10^{18}$

蒟蒻的思路

$DP$，令所求为 $f_{n,m}$，转移显然.

初值： $f_{1,m}=\frac{m(m+1)}{2}$

转移： $f_{n,m}=10\times(\sum\limits_{i=1}^{m}{f_{n-1,i}})+\frac{m(m+1)(nm+1)}{n(n+1)(n-1)}C_{n+m-1}^{n-2}$

时间复杂度：$O(n)$

巨佬的思路

显然有 $f_{n,6}=\frac{(n+5)(n+4)(n+3)(n+2)((9n+59)10^n-54n-59)}{9720}$，$f_{n,m}$ 不难求出.

时间复杂度：$O(\log n)$

Question

如何求得 $f_{n,m}$ 的通式？