PROBLEM LINKS:
DIFFICULTY:
SimpleEasy
PREREQUISITES:
Linear Recurrences, Matrix Exponentiation
PROBLEM:
There are infinite coins of two types  of value 1 and of value 2. All coins have two sides  heads and tails. You’re to find out number of ways of arranging some coins such that their sum is equal to N (input) and the first coin is heads up.
QUICK EXPLANATION:
Let f(N) denote number of ways of arranging some coins such that their sum is equal to N and the first coin is heads up. Then it can be shown that f(N) = 2 (f(N1) + f(N2) ) with f(1) = 1 and f(2) = 3. Using matrix exponentiation, f(N) can be computed in time O(log N).
DETAILED EXPLANATION:
Let f(n, H) denote the number of ways of arranging coins such that their sum is
n, and the first coin is heads up. Similarly let f(n, T) denote the number of
ways of arranging coins such that their sum is n and first coin is tails up.
Our original problem is to find out f(n, H).
Here are our three claims:

f(n, H) = f(n, T)

f(n, H) = f(n1, H) + f(n1, T) + f(n2, H) + f(n2, T)

f(n, H) = 2 * ( f(n1, H) + f(n2, H) )
Let’s see why each of these claims hold:

f(n, H) = f(n, T)
This is true because if we invert every coin of an arrangement with sum of n and
first coin heads up, we get an arrangement with sum of n with first coin tails
up. It is easy to see that it is infact a bijection. Hence the claim. 
f(n, H) = f(n1, H) + f(n1, T) + f(n2, H) + f(n2, T)
This is the chief step of the problem : Let’s look at a particular arrangement
with sum of n and first coin heads up. First coin is either of value 1 or of
value 2. In first case, sum of remaining coins is n1 and their first coin could
be either heads up or heads down. f(n1, H) + f(n1, T) account for such case.
In other case, when first coin is of value 2, sum of remaining coins is n2 and
they could either be heads up or tails up. f(n2, H) + f(n2, T) account for
these. So total : f(n, H) = f(n1, H) + f(n1, T) + f(n2, H) + f(n2, T) holds. 
f(n, H) = 2 * ( f(n1, H) + f(n2, H) )
This follows from claims 1 and 2 naturally
Now we can drop H from the notation to get f(n) = 2 f(n1) + 2 f(n2) with base
case of this recurrence as f(1) = 1 and f(2) = 3. We can use matrix
exponentiaion to solve for this recurrence. For those of you who don’t know
this very useful technique, I’m providing a short description here itself.
Let’s write it in form of matrices:
[ f(n) f(n1) ] = [ f(n1) f(n2) ] *  2 1 
 2 0 
You can verify that this is nothing but the recurrence we just wrote. Special
property of writing it in this form is we [ f(n1) f(n2) ] is exactly of the
same form as [ f(n) f(n1) ] and so we can in turn expand it to get:
[ f(n) f(n1) ] = [ f(n2) f(n3) ] *  2 1  *  2 1 
 2 0   2 0 
We can continue expanding term on right handside till we get :
[ f(n) f(n1) ] = [ f(2) f(1) ] *  2 1 ^(n2)
 2 0 
We can do a matrix exponentiation in time O(log N) using repeated squaring. So
we can find out f(N) as well in O(log N) time as well. As we’ve to report final
answer modulo (10^9 + 7), we would do all operations modulo (10^9 + 7)
SETTER’S SOLUTION:
Can be found here.
TESTER’S SOLUTION:
Can be found here.
RELATED PROBLEMS:
Codechef Chess Pushing Game
Codechef  Chef’s New Pet
REFERENCES: