# PROBLEM LINK:

# DIFFICULTY

EASY

# PREREQUISITES

Math, Repeated Squaring, Fibonacci Numbers

# PROBLEM

Find the number of ways to go from 0 to N, taking steps of 1 or 2, and taking exactly 1 back-step on the way of -1 or -2.

# QUICK EXPLANATION

Let us assume that Ciel takes `k`

steps forward, then one back, and the rest forward.

The number of ways she can accomplish this is `fib(k) * [ fib(N-k + 1) + fib(N-k + 2) ]`

; since she can take only 1 or 2 steps back.

We have to find a summation of the above sequence for all k between 1 and N-1 inclusive. We can see that this needs to us to find summation of the form

∑_{k = 0 to N}`fib(k)*fib(N-k)`

This is also known as the convolution of the fibonacci series onto itself. Once we know how to solve this convolution efficiently, we can solve the problem.

# EXPLANATION

There are several ways `F(N) =`

∑_{k = 0 to N}`fib(k)*fib(N-k)`

can be found.

Formulas regarding the same have been listed on Wikipedia as well as OEIS. Finding a couple of smaller values and searching on OEIS is a solution to many a problem that asks you to find the result for a sequence of numbers.

If you’re into math, then using the concept of fibonacci polynomials, one can derive several relations as outlined in this wonderful paper.

### I. F(N) = F(N-1) + F(N-2) + fib(N)

You can use the above identity and build a `4x4`

matrix as follows

|1 1 0 0| [F(N) F(N-1) fib(N) fib(N-1)] = [F(N-1) F(N-2) fib(N-1) fib(N-2)] * |1 0 0 0| |1 0 1 1| |1 0 1 0|

Now you can use matrix exponentiation to calculate `F(N)`

till the desired N to solve the problem.

### II. F(N) = 2*F(N-1) + F(N-2) - 2*F(N-3) - F(N-4)

Similar to (I) you can construct a 4x4 matrix and use matrix exponentiation.

4x4 matrix and its exponentiation leads to slightly larger constants and needs several micro optimizations to stay within the time limit. Thus, a better approach is to not need to do matrix exponentiation over 4x4 matrices at all, as outlined in (III) below.

### III. 5*F(N) = (n - 1)*fib(N + 1) + (n + 1)*fib(N - 1)

This elegant result is derived in this paper. Note that they assume fib[0] as 0 and fib1 as 1.

Using the above result we can say that we need to find

∑_{k = 1 to (N-1)}`fib(k+1) * [fib(N-k + 2) + fib(N-k + 3)]`

or ∑_{k = 1 to (N-1)}`fib(k+1) * fib(N-k + 4)`

We can rewrite the above as

`F(N+5) - fib(0)*fib(N+5) - fib(1)*fib(N+4) - fib(N+1)*fib(4) - fib(N+2)*fib(3) - fib(N+3)*fib(2) - fib(N+4)*fib(1) - fib(N+5)*fib(0)`

`= F(N+5) - 2*fib(N+4) - fib(N+3) - 2*fib(N+2) - 3*fib(N+1)`

A fibonacci number can be calculated by doing matrix exponentiation of a `2x2`

matrix, which is very fast. We cal find fib(N+1) and fib(N) through one exponentiation of the matrix representation of fibonacci numbers and calculate fib(N+2), fib(N+3), fib(N+4), fib(N+5) and fib(N+6) from them.

You may notice that calculating F(N) requires you to divide an integer by 5. Since we maintain modulo all along to avoid overflows, we must calculate the division modulo 1000000007 as well.

This can be accomplished by finding the modular multiplicative inverse of 5, modulo 1000000007.

# SETTERS SOLUTION

Can be found here

# TESTERS SOLUTION

Can be found here