- 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.