class ModularArithmetic(val mod: Long) {
class Mod(val value: Long) {
override val toString = value.toString
}
implicit def fromMod(mod: Mod): Long = mod.value
implicit def toMod(x: Long): Mod = new Mod(x%mod)
val factorial: IndexedSeq[Mod] = {
val N = 5500
val f = Array.ofDim[Mod](N)
f(0) = 1L
(1 until N).foreach(i => f(i) = f(i-1) * i)
f
}
def modularInverse(n: Long): Mod = BigInt(n).modInverse(mod).toLong //If mod is prime override this with BigInt(n).modPow(mod - 2, mod).toLong
def modDiv(a: Long, b: Long): Mod = a * modularInverse(b)
def permutations(n: Int, k: Int): Mod = modDiv(factorial(n), factorial(n - k))
def combinations(n: Int, k: Int): Mod = modDiv(permutations(n, k), factorial(k))
}