Yet Another Number Sequence
题意翻译
# 题目描述
所有人都知道什么是斐波那契数列(相信洛谷的童鞋们都知道),他是由以下数列表示的:
$F_1=1,F_2=2$
通项公式:F[i]=F[i-1]+F[i-2]
我们要找到一个新数列$A_i(k)$,其通项公式是:
$A_i(k)=F_i*i^k(i>=1)$
我们找到了你,希望你求出这个算式的结果:
# $A_1(k)+A_2(k)+...+A_n(k)$
这个算式的结果会很大,所以要求你将结果对$10^9+7$取余。
# 输入输出格式
## 输入
输入两个数$n,k(1<=n<=10^{17},1<=k<=40)$.
## 输出
输出仅一行,代表算式的结果(对$10^9+7$取余)。
题目描述
Everyone knows what the Fibonacci sequence is. This sequence can be defined by the recurrence relation:
$ F_{1}=1,F_{2}=2,F_{i}=F_{i-1}+F_{i-2} (i>2). $ We'll define a new number sequence $ A_{i}(k) $ by the formula:
$ A_{i}(k)=F_{i}×i^{k} (i>=1). $ In this problem, your task is to calculate the following sum: $ A_{1}(k)+A_{2}(k)+...+A_{n}(k) $ . The answer can be very large, so print it modulo $ 1000000007 $ $ (10^{9}+7) $ .
输入输出格式
输入格式
The first line contains two space-separated integers $ n $ , $ k $ $ (1<=n<=10^{17}; 1<=k<=40) $ .
输出格式
Print a single integer — the sum of the first $ n $ elements of the sequence $ A_{i}(k) $ modulo $ 1000000007 $ $ (10^{9}+7) $ .
输入输出样例
输入样例 #1
1 1
输出样例 #1
1
输入样例 #2
4 1
输出样例 #2
34
输入样例 #3
5 2
输出样例 #3
316
输入样例 #4
7 4
输出样例 #4
73825