Panic! at the Disco

You are given a $K \times K$ matrix $M$. For each $r$ and $c$ ($1 \le r, c \le K$), let's denote the element in the $r$-th row and $c$-th column by $M_{r, c}$. You are also given three integers $N$, $a$ and $d$. Let's define a $K \times K$ matrix $$S = \sum_{i=0}^N F_{a + i \cdot d} \cdot M^i \,.$$ Here, $M^0$ is the identity matrix and for any non-negative integer $i$, $F_i$ is the $i$-th Fibon