CF392C Yet Another Number Sequence

众所周知，Fibonacci 数列定义如下： $ F_{1}=1，F_{2}=2，F_{i}=F_{i-1}+F_{i-2} (i>2) $。我们定义一个新数列 $ A_{i}(k) $，其公式为： $ A_{i}(k)=F_{i} \times i^{k} (i \geq 1) $。在本题中，你的任务是计算以下求和式的结果：$ A_{1}(k)+A_{2}(k)+\cdots+A_{n}(k) $。由于答案可能非常大，请输出其对 $ 1000000007 $ $ (10^{9}+7) $ 取模后的结果。

第一行包含两个用空格分隔的整数 $ n $ 和 $ k $，满足 $ 1 \leq n \leq 10^{17}，1 \leq k \leq 40 $。

输出一个整数，表示数列 $ A_{i}(k) $ 的前 $ n $ 项和对 $ 1000000007 $ $ (10^{9}+7) $ 取模后的结果。

由 ChatGPT 5 翻译