Freaks City

This article addresses the problem of finding the coefficient of the $x^n y^m$ term in the expansion of the polynomial $(ax + by)^k$. The solution involves applying the binoimal theorem and calculating combinations modulo 10007. Binomial Theorem Application The binomial theorem states that $(x+y)^k = \sum_{i=0}^{k} \binom{k}{i} x^{k-i} y^i$. In ...

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