Working with fractions usually we get a hint like "You should compute P⋅Q−1 modulo 109+7, where Q−1 denotes the multiplicative inverse of Q modulo 109+7."
So, I more (or less) understood what that means. I can express, say 1/5 by the number 400000003. I can calculate that number using https://www.geeksforgeeks.org/fermats-little-theorem/ implemented by some code I found somewhere (see below).
BUT: How do I add (and/or multiply) fractions with huge values?
i.e. how to calculate and express something like this: Let E=10e9+7 Then, how to express: ((E+1) / (E+2)) + ((E+3) / (E+4))
Any hint or link to an understandable explenation would be really helpfull. Thanks.
The code I use so far, based on that fermat thing: ~~~~~ class Inv { companion object { val defaultMod = 1000000007L var MOD = defaultMod
fun toPower(a: Long, p: Long, mod: Long = MOD): Long { var a = a var p = p var res = 1L while (p != 0L) { if (p and 1 == 1L) res = res * a % mod p = p shr 1 a = a * a % mod } return res } fun inv(x: Long, mod: Long = MOD): Long { return toPower(x, mod - 2) } fun simpleInf(nenner: Long, zaehler: Long): Long { return nenner * Inv.inv(zaehler) % Inv.MOD } } }
~~~~~