T217223 [CZOI2022]狄利克雷卷积

这一天，明陌在牛客网上看到了一道有趣的题，也十分的简单，于是三下五除二打好了代码，提交——全部超时······ 所以，明陌把那道题（的题干）搬到这场比赛中，相信大家可以把它切掉

求 $F(n) = Σ_{i=1}^n f_i \times x^i$ 其中 $f_i = a \times f_{i-1} + b \times f_{i-2} $$（i>=2）$ $f_0 = 0 , f_1 = 1 $

输入一行四个数分别是 $n$ $a$ $b$ $x$

输出 $F(n)$ $mod$ 1e9+9

对于前 $30\%$ 的数据，$n \le 10，a = b = 1，x \le 5$ 对于另外 $20\%$ 的数据，$b = 0， x = 1$ 对于前 $80\%$ 的数据，$n \le 10^6$ 对于 $100\%$ 的数据，$n \le 2×10^7，a, b, x \le 10^9$ ------------ 以上是想要造的数据 下面是现在已经做好的数据（也就是现在的数据） 对于前 $30\%$ 的数据，$n \le 10$ 对于前 $50\%$ 的数据，$n \le 10000$ 对于 $100\%$ 的数据，$n \le 10^7 $ 前七个测试点的内存限制为256MB 对于倒数第二个和倒数第三个测试点，内存不能超过128MB 对于最后一个测试点，内存不能超过64MB