Help in a spoj problem

Can anyone please help me with this spoj problem Colorcat. I found some hint on codeforces (codeforces hint ), but I am not able to understand how to use FFT for matrix multiplication.

I just know that FFT is used to multiply two polynomials in O(nlogn) time.