# Crunchy
We are given a small Python program which computes the flag:
```def crunchy(n):    if n < 2: return n    return 6 * crunchy(n - 1) + crunchy(n - 2) g = ...  # a _really_ big numberprint("Your flag is: INSA{%d}"%(crunchy(g)%100000007))```
Running this, of course, won't get us anywhere with the exponentiallyslow implementation of `crunchy`. A simple improvement would be tocache computed vaues of `crunchy(n)`, but that reduces the complexityto linear, which is still not nearly enough with the hundred-digitparameter.
Since `crunchy` is a linear recurrence, we can compute it inlogarithmic time. We can express the mapping from $(c(n), c(n-1))$ to$(c(n+1), c(n))$ (where $c$ is the function) as a matrix multiplication:
$$ \begin{pmatrix}c(n+1)\\c(n)\end{pmatrix} =\begin{pmatrix}6&1\\1&0\end{pmatrix}\begin{pmatrix}c(n)\\c(n-1)\end{pmatrix} $$
If we expand the right-hand side of this equation $n-1$ times, we willget:
$$ \begin{pmatrix}c(n+1)\\c(n)\end{pmatrix} =\begin{pmatrix}6&1\\1&0\end{pmatrix}^n\begin{pmatrix}c(1)\\c(0)\end{pmatrix} $$
Since we know the values of $c(1)$ and $c(0)$, all that remains is tocompute the exponentiated matrix. We can do this in$\mathcal{O}(\log{n})$ multiplications by [repeatedsquaring](https://en.wikipedia.org/wiki/Exponentiation_by_squaring),which is completely reasonable for the input value of `g` (a fewhundreds of multiplications).
Note that all multiplications should be done modulo $10^9 + 7$ insteadof only doing so at the end -- otherwise, the intermediate values willbe to large to work with (they grow exponentially).