Basics: dividing under a prime modulus

Many problems say "the answer is a fraction p / q; print it modulo MOD = 1_000_000_007". That means: return the number x in [0, MOD) with x · q ≡ p (mod MOD), i.e. p · q⁻¹ mod MOD. You can't just do p // q or p / q: modular arithmetic has no floats, and integer division doesn't commute with %.

Write two functions:

1. frac_mod(p: int, q: int) -> int: the fraction p / q modulo MOD. p may be negative or huge; q is never a multiple of MOD, but it may be negative too.
2. average_mod(nums: list[int]) -> int: the average of a non-empty list, as a fraction modulo MOD.

frac_mod(6, 3)        # 2
frac_mod(1, 2)        # 500000004   (2 · 500000004 = 1000000008 ≡ 1)
frac_mod(-1, 2)       # 500000003
average_mod([1, 2])   # 500000005   (3/2)
average_mod([4, 4, 7])  # 5

Since MOD is prime, Fermat's little theorem gives the inverse: q⁻¹ ≡ q^(MOD-2). Python's pow(q, MOD - 2, MOD) (or pow(q, -1, MOD)) computes it in O(log MOD). Reduce with % MOD so the result lands in [0, MOD); Python's % already returns a non-negative value for a positive modulus.

Constraints: |p|, |q| <= 10^18, q % MOD != 0; 1 <= len(nums) <= 10^5, |nums[i]| <= 10^18.