You do some matrix maltiplication and get an answer in the form (a%10^9)/(b%10^9), but it is not guaranteed that gcd (a, b) == 1. How to get irreducible fraction now???

it can be proved be deduction that  if a/b is irreducible fraction then  a[i]+a/b is also irreducible fraction

problem descrption means original a/b is irreducible not after mod...