help in understanding matrix expo. in problem 351C

prob : http://codeforces.com/contest/351/problem/C

I’ve read the editorial but didn’t understand the matrix exponentiation part. can someone please explain that part.

hey i tried but didn’t get it.
but u can help me by explaining ur chef and average on a tree.
ur soln link https://www.codechef.com/viewsolution/17186664

@gyanendra371 My idea’s explanation : https://discuss.codechef.com/questions/122011/l56avg-editorial/122201