**- A Bittersweet Day!**

Sometimes you want to be happy, but something sad inside of you has more control than your own on your feelings. Today we had a different day , bitter things happened , sweet news received.

.

__The__Bitter Part : Today Faraz was depressed and he attempted suicide , he was on the roof of an 14 floors apartment and I was screaming for help buuuuut suddenly ... :( ... OK, I exaggerated again , I don't know why but i like it :) Actually he was depressed but I didn't know why and he didn't talk much. We went out for hours to have a rest after some tough days. Long story short__things were not going well__..

__The__Sweet Part : Finally, we received the SnackDown email about sending T-Shirts and Goodies. We don't know what will be the goodies, but Faraz predicts that they will be Peppers because SnackDown is a Hindi competition ;) We had got rank 227 out of 13500 teams of all over the world.

**- Matrix Multiplication**

One of the must known methods for Codeforces D and higher problems is Matrix Multiplication.

Let's consider it with a simple example. Suppose you want to find the 10^18'th Fibonacci Number (modulo 1e9+7). How will you find it ?

I want to solve it with mentioned method. We need a master matrix[M] and a coefficient matrix[C] (these name are not official !).

In M we will put two of the consecutive Fibonacci numbers. C must be a matrix that M*C receives the next 2 consecutive elements of the sequence.

Also we know that matrix multiplication has associative property , so we can do this :

Well , We reduced the problem to finding the x'th power of the matrix C and multiplying it to M ! Now How we can find x'th power of the matrix fast ?

Yes , Binary Exponentiation . As an example :

2^12 = 2^6 * 2^6

2^6 = 2^3 * 2^3

2^3 = 2^1 * 2^1 * 2 = 8

2^6 = 8 * 8 = 64

2^12 = 64 * 64 = 4096

OK this was a short explanation about Matrix Multiplication , I recommend you to read

__these__well-written links for more details :- Suhendry's Blog ( Some simple applications and codes )

- Fushar's Blog ( Advanced examples )

And some problems to solve :

You may check the second problem's implementation as a sample code.