sub invert {
    my ($n, $p)=@_;
    # Trusting $p to be a prime...
    my sub expp {
        my ($n, $m)=@_;
        return 1 unless $m;
        ($m%2 ? $n : 1) * expp($n, $m >> 1)**2 % $p;
    }
    expp($n, $p-2);
}