Hi all.

I try to solve this problem. It seems that it can be easily solved with matrix exponentiation. I wrote the code in Java which worked on my computer and in Codeforces, but surprisingly gave RE1 in Timus. Even if this test differs from the input, I can't find where can it happen. Couldn't you help me with this?

Thanks in advance.