T234596 楼梯问题2（困难）

递推-矩阵乘法

有$n$级楼梯，每次可以上$1 \dots m$级，求有多少种上楼梯的方法。 输出答案对$10^9 +7$取模后的数。

两个正整数$n$和$m$。

一个正整数。

对于30%的数据，$1 ≤ n ≤ 10^6$。 对于100%的数据，$1 ≤ n ≤ 10^{18}$，$1 ≤ m ≤ 100$。