Hi everybody!

I recently was in a programming contest. There were 20 tasks, and one of them was as follows:

In resume, you have C chairs and P pairs of chairs are given. The pairs P(i, j) denote the probability of changing from chair i to chair j. You are sitting in one of these chairs, and every second you have to move to another one.

Then you have Q queries, each with two integers C_i, s , where C_i is the initial chair you are seated and you have to tell the chair that has the highest probability of being seated in after s seconds (after s changes).

1 ≤ C_i ≤ 50

1 ≤ s ≤ 100000000

At first, I thought this was a simple problem, solvable using matrix exponentiation. First creating a matrix M, where M_ij = P(i, j). The answer should be in the C_i row of the resulting matrix M^S, but the problem has the next important requirement:

You have to output the probability as an irreducible fraction. Worst of all, you have to output ONLY the very last digits of numerator and denominator...

For example: 15/23 -> 5/3

I tried using Java BigInteger, doing reductions with gcd, but it was way too slow.

This is a very interesting requirement (yet a very tough one too, at least for me). Any help will be very appreciated :)

(The contest has already ended, I'm not cheating, and I struggle a lot of hours with this tasks :( )