DZY Loves Fibonacci Numbers,CF - 446C

//codeforces - DZY Loves Fibonacci Numbers
Btw:

We can do this without matrix multiplication:

1) F(a, b, k) = a * fk - 2 + b * fk - 1 -- k-th element of general Fibonacii sequences starting with a, b, where fi — i-th Fibonacci numbers (starting from 1, 1).

2) sum of first k members of general Fibonacci sequence Fi equals to Fk + 2 - F2.

So we only need to precalculate Fibonacci numbers.