Python 代码

n, p = map(int, input().split())

def qmi(a, b, p):
    res = 1
    while b:
        if b & 1: res = res * a % p
        b >>= 1
        a = a * a % p
    return res

primes = []
st = [True] * (2*n+1)

def find_primes(n):
    for i in range(2, n+1):
        if st[i]: primes.append(i)
        for pi in primes:
            if pi > n//i: break
            st[pi*i] = False
            if i % pi == 0: break

def get(a, b):
    cnt = 0
    while a:
        cnt += a // b
        a //= b
    return cnt

def C(a, b, p):
    res = 1
    for pi in primes:
        s = get(a, pi) - get(b, pi) - get(a-b, pi)
        res = res * qmi(pi, s, p) % p
    return res
find_primes(2*n)
print((C(2*n, n, p) - C(2*n, n-1, p)) % p)