Hey there,

I just took a programming contest and received a pretty interesting mathematical problem.

To sum up, you are given two numbers n and k (1 <= n <= 10^18, 1 <= k <= 10^6).

Assume that F(i) is the i-th number in the Fibonacci sequence

E.g: F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, e.t.c.

Calculate the sum S of the first n Fibonacci numbers raised to the power of k.

Or in terms of pseudocode:

S = 0
for (i = 1 -> n)
    S = S + F(i)^k

Print the answer modulo 998244353. Is there any good approach to this problem? Thank you for reading!