最近看到一道站外题：

有序列 $f_i=a_1f_{i-1}+a_2f_{i-2}+a_3f_{i-3}+\cdots+a_kf_{i-k}+b,(当i>k时)$ 输入$f$的前$k$项,$n$,数列$a$,常数$b$,和$c$,求出$f_n\mod c$。

数据范围： $n\leq 10^{18},c\leq 10^{18},k\leq 5000$,

$f$的前$k$项,$a$序列中的值和常数$b$都在long long 范围内。

这题该怎么做？