py-num

def fact(n, M):
    ans = 1
    for i in range(1, n+1):
        ans = (ans*i%M)%M
    return ans

def mode_inv(n, M):
    return pow(n, M-2, M)

def npr(n, r, M):
    return (fact(n, M)*mode_inv(fact(n-r, M), M)) % M

def ncr(n, r, M):
    return (npr(n, r, M)*mode_inv(fact(r, M), M)) % M

def permute(d, M):
    n = sum(list(d.values()))
    ans = fact(n, M)
    deno = 1
    for i in d.values():
        deno = (deno*fact(i, M)) % M
    ans = (ans*mode_inv(deno, M)) % M
    return ans