pjt33

#!/usr/bin/pypy3

from heapq import heappush, heappop

def mod_inv(a: int, m: int) -> int:
	lastremainder, remainder = a % m, m
	x, lastx, y, lasty = 0, 1, 1, 0
	while remainder:
		lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
		x, lastx = lastx - quotient*x, x