Hi everybody!

I recently was in a programming contest. There were 20 tasks, an 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 been 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. The answer should be in the C_i row of the resulting matrix, 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.