Freaks City

Given (n,c,k), compute (\sum_{i=0}^n f_{ic}^k) modulo (p=10^9+9), where (f_i) is the (i)-th Fibonacci number. Constraitns: (n,c\in[1,10^{18}]), (k\le 10^5), (T\le 200), time limit 3 seconds. Use the closed-form expression for Fibonacci numbers: (f_i = \frac{1}{\sqrt5}\left(\alpha^i - \beta^i\right)), where (\alpha = \frac{1+\sqrt5}{2}), (\beta ...