I was trying to solve this problem, find the n'th term of the following recurrence:

F(n) = a*F(n-1) + b*F(n-2) + c*F(n-3) + n*n*(n+1)

a,b,c and the first 3 numbers in the sequence are given as the input, n can be upto 10^18 . I know that problems involving linear recurrences can be solved using matrix exponentiation, even when there are multiple sequences involved. So, in this case, if I could somehow express n*n*(n+1) as a linear recurrence as well, solving this problem becomes simple. However, I'm not able to do that, can someone help me with this ? Also, if a method to find a recurrence relation, given a closed form, exists, please mention that as well. Thanks in advance.

Hopefully, this helps:

https://codeforces.com/blog/entry/19046

Got it, thank you so much