CF392C Yet Another Number Sequence

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) $ .

N/A

N/A