I dont wanna give too much away but did you know SymPy has a really cool function called mod_inverse? It works well for really large numbers in case you aren’t a number theory guru.
I liked this challenge, made me feel stupid but like, in a good way?