In Python3.8 and later, the inverse mod can be calculated with the built-in function pow.

Overview

It is an inverse modulo operation that is often used in competitive programming, but since Python 3.8 it seems that it can be calculated using the built-in function pow.

Until now, it was necessary to create your own function to find the remainder of the inverse element by referring to the method described in the following article. A special feature on how to find "too much divided by 1000000007"! ~ From inverse element to discrete logarithm ~ (Qiita)

For example in Python 3.8 or later

38^{-1}\,\,mod\,\,97

When you want to calculate

pow(38, -1, 97)

You will be able to calculate with.

Check the official documentation

Python3.7 Built-in functions-pow (x, y [, z])

pow(x, y[, z]) Returns the y-th power of x; if z exists, returns the remainder of z for the y-th power of x ~ Omitted ~ If there is> z, x and y must be of integer type and y must be non-negative.

Python3.8 Built-in functions-pow (base, exp [, mod])

pow(base, exp[, mod]) Returns the exp-th power of base; if there is a mod, returns the remainder of mod for the exp-th power of base ~ Omitted ~ For int operands base and exp, if mod is present, mod must also be of integer type and mod must be nonzero. If mod is present and exp is negative, base must be relatively prime to mod. In that case, pow(inv_base, -exp, mod) is returned, where inv_base is an inverse to base modulo mod.

The 3.7 documentation states that the `` pow (x, y, z) argument y (ʻexp) must be non-negative if there is an argument z ( mod). , That description has been removed in the 3.8 documentation. The 3.8 documentation states that when the pow (base, exp, mod) argument ʻexpis negative, thebase and modmust be relatively prime, and the argument ʻexpAllows negative numbers even with mod.

I will actually check it.

keigo0205@MacBook-Pro ~ % python --version
Python 3.8.2
keigo0205@MacBook-Pro ~ % python
Python 3.8.2 (default, Mar 24 2020, 11:35:26) 
[Clang 11.0.0 (clang-1100.0.33.17)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> pow(38, -1, 97)
23
>>> 23 * 38 % 97 == 1
True
>>> exit()

keigo0205@MacBook-Pro ~ % python --version
Python 3.7.7
keigo0205@MacBook-Pro ~ % python
Python 3.7.7 (default, Mar 24 2020, 13:42:02) 
[Clang 11.0.0 (clang-1100.0.33.17)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> pow(38, -1, 97)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: pow() 2nd argument cannot be negative when 3rd argument specified
>>> exit()

That's right···

Try to solve the problem of using the inverse mod with AtCoder.

Let's solve ABC159-D --Bouquet. AtCoder's Python is version 3.8.2.

Problem summary Given the natural numbers n and less than that, the different natural numbers ʻa and b. Find the answer of the following formula divided by 10 ** 9 + 7. However, note that ʻa and b are less than or equal to 2 * 10 ** 5.

2^n - 1 - nCa - nCb

Answer example

n, a, b = list(map(int, input().split()))
MOD = 10**9 + 7

# 1!From max(a, b)!The inverse element up to is divided by MOD
#n to n-max(a*b)Divide by MOD to find the remainder.
fact = {}
fact[n] = n
fact[n - 1] = fact[n] * (n - 1) % MOD

inv_fact = [0] * (max(a, b) + 1)
inv_fact[1] = 1

for i in range(2, max(a, b) + 1):
    fact[n - i] = fact[n - i + 1] * (n - i) % MOD
    inv_fact[i] = inv_fact[i - 1] * pow(i, -1, MOD) % MOD

subtrahend = 1 + fact[n - a + 1] * inv_fact[a] + fact[n - b + 1] * inv_fact[b]
minuend = pow(2, n, MOD)

print((minuend + 2 * MOD - subtrahend) % MOD)

Summary

I introduced it because the function of the built-in function was extended in Python 3.8. You should read the official documentation on a regular basis.

Personally, I'm happy to be able to simply write the inverse mod without having to bring my own function.