Problem:


Balls and Boxes 3

  
BallsBoxesAny wayAt most one ballAt least one ball

  
DistinguishableDistinguishable123

  
IndistinguishableDistinguishable456

  
DistinguishableIndistinguishable789

  
IndistinguishableIndistinguishable101112

Problem

You have $n$ balls and $k$ boxes. You want to put these balls into the boxes.

Find the number of ways to put the balls under the following conditions:

  
Each ball is distinguished from the other.

  
Each box is distinguished from the other.

  
Each ball can go into only one box and no one remains outside of the boxes.

  
Each box must contain at least one ball.

Note that you must print this count modulo $10^9+7$.

Input

$n$ $k$

The first line will contain two integers $n$ and $k$.

Output

Print the number of ways modulo $10^9+7$ in a line.

Constraints

  
$1 \le n \le 1000$

  
$1 \le k \le 1000$

Sample Input 1

4 3

Sample Output 1

36

Sample Input 2

10 3

Sample Output 2

55980

Sample Input 3

100 100

Sample Output 3

437918130



Sample input:
4 3


Sample output:
36

Submission status: Accepted

Solution code:
#!/usr/bin/env python

import sys
import math
import itertools as it
from collections import deque

sys.setrecursionlimit(10000000)

MOD = 10 ** 9 + 7
n, k = map(int, raw_input().split())

def fact(N):
    if N <= 1:
        return 1
    return fact(N - 1) * N

def pow(N):
    ret = 1
    for i in range(n):
        ret *= N
        ret %= MOD
    return ret

C = 0
for i in range(k - 1, 0, -1):
    num = fact(k) / fact(i) / fact(k - i) * pow(i)
    if (i - k) % 2 == 1:
        num *= -1
    C += num
print (pow(k) + C) % MOD

Submission status: Accepted

Solution code:
class Twelvefold(): #n <= 1000程度
    def __init__(self, n, mod):
        self.mod = mod
        self.fct = [0 for _ in range(n + 1)]
        self.inv = [0 for _ in range(n + 1)]
        self.stl = [[0 for j in range(n + 1)] for i in range(n + 1)]
        self.bel = [[0 for j in range(n + 1)] for i in range(n + 1)]
        self.prt = [[0 for j in range(n + 1)] for i in range(n + 1)]
        self.fct[0] = 1
        self.inv[0] = 1
        self.stl[0][0] = 1
        self.bel[0][0] = 1
        for i in range(n):
            self.fct[i + 1] = self.fct[i] * (i + 1) % mod
        self.inv[n] = pow(self.fct[n], mod - 2, mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i + 1] * (i + 1) % mod
        for i in range(n):
            for j in range(n):
                self.stl[i + 1][j + 1] = self.stl[i][j] + (j + 1) * self.stl[i][j + 1]
                self.stl[i + 1][j + 1] %= mod
        for i in range(n):
            for j in range(n):
                self.bel[i + 1][j + 1] = self.bel[i + 1][j] + self.stl[i + 1][j + 1] % mod
                self.bel[i + 1][j + 1] %= mod
        for j in range(n):
            self.prt[0][j] = 1
        for i in range(n):
            for j in range(n):
                if i - j >= 0:
                    self.prt[i + 1][j + 1] = self.prt[i + 1][j] + self.prt[i - j][j + 1]
                else:
                    self.prt[i + 1][j + 1] = self.prt[i + 1][j]
                self.prt[i + 1][j + 1] %= mod

    def solve(self, element, subset, equate_element=False, equate_subset=False, less_than_1=False, more_than_1=False):
        assert not less_than_1 or not more_than_1
        n = element
        k = subset
        a = equate_element
        b = equate_subset
        c = less_than_1
        d = more_than_1
        id = a * 3 + b * 6 + c + d * 2
        tw = [self.tw1, self.tw2, self.tw3, self.tw4, self.tw5, self.tw6, self.tw7, self.tw8, self.tw9, self.tw10, self.tw11, self.tw12]
        return tw[id](n, k)

    def tw1(self, n, k):
        return pow(k, n, self.mod)

    def tw2(self, n, k):
        if k - n < 0: return 0
        return self.fct[k] * self.inv[k - n] % self.mod

    def tw3(self, n, k):
        return self.stl[n][k] * self.fct[k] % self.mod

    def tw4(self, n, k):
        if k == 0: return 0
        return self.fct[n + k - 1] * self.inv[n] * self.inv[k - 1] % self.mod

    def tw5(self, n, k):
        if k - n < 0: return 0
        return self.fct[k] * self.inv[n] * self.inv[k - n] % self.mod

    def tw6(self, n, k):
        if n - k < 0 or k == 0: return 0
        return self.fct[n - 1] * self.inv[k - 1] * self.inv[n - k]

    def tw7(self, n, k):
        return self.bel[n][k]

    def tw8(self, n, k):
        if k - n < 0: return 0
        return 1

    def tw9(self, n, k):
        return self.stl[n][k]

    def tw10(self, n, k):
        return self.prt[n][k]

    def tw11(self, n, k):
        if k - n < 0: return 0
        return 1

    def tw12(self, n, k):
        if n - k < 0: return 0
        return self.prt[n - k][k]

n, k = map(int, input().split())
t = Twelvefold(1000, 10**9 + 7)
print(t.solve(n, k, 0, 0, 0, 1))

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def prepare(n, MOD):
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


def main():
    n, k = ns()

    # 使い方
    facts, invs = prepare(k, MOD)

    ans = 0
    for i in range(k):
        tmp = pow(k - i, n, MOD) * (facts[k] * invs[i] * invs[k - i] % MOD)
        tmp %= MOD
        if i % 2:
            ans -= tmp
        else:
            ans += tmp
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = int(1e9) + 7
MAXN = 2000
comb = [[0 for i in range(MAXN)] for j in range(MAXN)]

# 組み合わせ(1e9+7で割る場合)
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 2000
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % MOD )
    inverse.append( ( -inverse[MOD % i] * (MOD//i) ) % MOD )
    g2.append( (g2[-1] * inverse[-1]) % MOD )

for i in range(MAXN):
    for j in range(MAXN):
        comb[i][j] = cmb(i, j, MOD)

N, K = map(int, input().split())
ans = 0
for i in range(1, K+1):
    rest = K - i
    val = comb[K][i] * pow(rest, N, MOD) % MOD
    if i % 2 == 1:
        ans = (ans + val) % MOD
    else:
        ans = (ans - val + MOD) % MOD
ans = (pow(K, N, MOD) - ans + MOD) % MOD
print(int(ans))

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10**9 + 7
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def combMod(n, r, p):
    numer = 1
    denom = 1
    for i in range(1, r+1):
        numer = numer * (n-r+i) % p
        denom = denom * i % p
    return numer * pow(denom, p-2, p) % p

def resolve():
    n, k = LI()

    if n >= k:
        ans = 0
        for i in range(k):
            ans += (-1) ** i * combMod(k, k - i, MOD) * pow(k - i, n, MOD)
            ans %= MOD
    else:
        ans = 0

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
mod=10**9+7
ans=0
cmb=K
for i in range(1,K+1):
	ans+=(-1)**(K-i)*cmb*pow(i,N,mod)%mod
	ans%=mod
	cmb=cmb*(K-i)*pow(i+1,mod-2,mod)
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
MOD = 10 ** 9 + 7

# 逆元の前計算
factorial = [1, 1]
inverse = [1, 1]
invere_base = [0, 1]
for i in range(2, K + 1):
    factorial.append((factorial[-1] * i) % MOD)
    invere_base.append((-invere_base[MOD % i] * (MOD // i)) % MOD)
    inverse.append((inverse[-1] * invere_base[-1]) % MOD)


# フェルマーの小定理を用いたMOD上Combination
def nCr(n, r):
    if (r < 0 or r > n):
        return 0
    r = min(r, n - r)
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


# 包除原理
ans = pow(K, N, MOD)
for r in range(1, K + 1):
    ans -= ((-1) ** ((r % 2) ^ 1)) * nCr(K, r) * pow(K - r, N, MOD) % MOD

print(ans % MOD)

Submission status: Accepted

Solution code:
class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


if __name__ == "__main__":
    N, K = map(int, input().split())
    mod = 10 ** 9 + 7
    U = 1000
    comb = Combination(U + 5, mod)

    total = pow(K, N, mod)
    ng = 0
    for i in range(1, K):
        pair = comb(K, i)
        cnt = pow(K - i, N, mod)
        if i % 2 == 0:
            ng -= pair * cnt
            ng += mod
            ng %= mod
        else:
            ng += pair * cnt
            ng %= mod

    ans = (total - ng + mod) % mod
    print(ans)

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7
EPS = 10 ** -10

class ModTools:
    """ 階乗・逆元用のテーブルを構築する """

    def __init__(self, MAX, MOD):
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        inverse = [1] * MAX
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, -1, -1):
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせ """

        if n < r: return 0
        r = min(r, n-r)
        numerator = self.fact[n]
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

    def nHr(self, n, r):
        """ 重複組み合わせ """

        return self.nCr(r+n-1, r)

    def nPr(self, n, r):
        """ 順列 """

        if n < r: return 0
        return self.fact[n] * self.inv[n-r] % self.MOD

    def div(self, x, y):
        """ MOD除算 """

        return x * pow(y, self.MOD-2, self.MOD) % self.MOD

N, K = MAP()

mt = ModTools(max(N, K)+1, MOD)
ans = 0
for i in range(K+1):
    if i % 2 == 0:
        ans += mt.nCr(K, i) * pow(K-i, N, MOD) % MOD
    else:
        ans -= mt.nCr(K, i) * pow(K-i, N, MOD) % MOD
print(ans%MOD)

Submission status: Accepted

Solution code:
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD


def way3(ball, box):
    """ball: True / box: True / constraints: 1 or more
    -> ans = (包除原理)
    """
    if ball < box:
        return 0
    ans = 0
    for i in range(box + 1):
        ans += pow(-1, i, MOD) * comb.combination(box, i) * pow(box - i, ball, MOD)
        ans %= MOD
    return ans


n, k = map(int, input().split())
MOD = 10 ** 9 + 7
comb = Combination(10 ** 4, MOD)

print(way3(n, k))

Submission status: Accepted

Solution code:
MOD = 1000000007
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)
    def __int__(self):
        return self.x

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __mod__(self, other):
        return (
            ModInt(
                other.x
            ) if isinstance(other, ModInt) else
            self.x
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
    
    def __iadd__(self,other):
        self.x += other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self

    def __isub__(self,other):
        self.x += ModInt(MOD - other.x) if isinstance(other, ModInt) else ModInt(MOD - other)
        return self

    def __imul__(self, other):
        self.x *= other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self
    
    def __ifloordiv__(self, other):
        self.x *= pow(int(other), MOD - 2, MOD)
        return self
    
    def factorical(self,n):
        tmp = ModInt(1)
        for i in range(n):
            tmp *= (i+1)
        return tmp
    
    #m:int MOD
    def modinv(self,a,m=MOD):
        b = m
        u = 1
        v = 0
        while(b):
            t = a//b
            a -= t * b
            a,b = b,a
            u -= t * v
            u,v = v,u
        return ModInt(u)

    def comb(self,n,r):
        n = int(n)
        r = int(r)
        if r > n or n < 0 or r < 0:
            return 0
        m = n+1
        nterms = min(r, n-r)
        numerator = ModInt(1)
        denominator = ModInt(1)
        for j in range(1, nterms + 1):
            numerator *= m - j
            denominator *= j
        return numerator * self.modinv(denominator.x)
        
if __name__ == "__main__":
    n,k = map(int,input().split())
    if n < k:
        print(0)
    else:
        ans = ModInt(0)
        v = ModInt(1)
        for i in range(k):
            if i%2:
                ans -= pow(k-i,n,MOD)*v
            else:
                ans += pow(k-i,n,MOD)*v
            v *= k-i
            v //= i+1
        print(ans)

Submission status: Accepted

Solution code:
#!python3
from math import factorial

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, K = iim()
    mod = 10**9 + 7
    if N < K:
        print(0)
        return
    elif N == K:
        print(factorial(N) % mod)
        return

    ans = 0
    cm = 1
    for i in range(K):
        ans += ((-1)**i) * cm * pow(K - i, N, mod)
        ans %= mod
        cm = cm * (K - i) // (i + 1)

    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys

mod=1000000007

n,k=[int(i) for i in input().split(" ")]



facts=[1 for i in range(n+k+1)]

for i in range(1,n+k+1):
    facts[i]=i*facts[i-1]

if n<k:
    print(0)
    sys.exit()

tables=[[-1 for i in range(k+1)] for j in range(n+1)]

def f(n,k):
    if k==1:
        return 1

    elif n==k:
        return facts[n]%mod

    elif tables[n][k]!=-1:
            return tables[n][k]

    else:
        retval=(k*f(n-1,k)+k*f(n-1,k-1))%mod
        tables[n][k]=retval
        return retval

print(f(n,k)%mod)

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def C(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def P(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[n-r] % self.mod

    def H(self, n, r):
        if n == 0 and r > 0: return 0
        return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.mod

    def rising_factorial(self, n, r):  # 上昇階乗冪 n * (n+1) * ... * (n+r-1)
        return self.fac[n+r-1] * self.facinv[n-1] % self.mod

    def stirling_first(self, n, k):  # 第 1 種スターリング数  lru_cache を使うと O(nk)  # n 要素を k 個の巡回列に分割する場合の数
        if n == k: return 1
        if k == 0: return 0
        return (self.stirling_first(n-1, k-1) + (n-1)*self.stirling_first(n-1, k)) % self.mod

    def stirling_second(self, n, k):  # 第 2 種スターリング数 O(k + log(n))  # n 要素を区別のない k グループに分割する場合の数
        if n == k: return 1  # n==k==0 のときのため
        return self.facinv[k] * sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def balls_and_boxes_3(self, n, k):  # n 要素を区別のある k グループに分割する場合の数  O(k + log(n))
        return sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def bernoulli(self, n):  # ベルヌーイ数  lru_cache を使うと O(n**2 * log(mod))
        if n == 0: return 1
        if n % 2 and n >= 3: return 0  # 高速化
        return (- pow(n+1, self.mod-2, self.mod) * sum(self.C(n+1, k) * self.bernoulli(k) % self.mod for k in range(n))) % self.mod

    def faulhaber(self, k, n):  # べき乗和 0^k + 1^k + ... + (n-1)^k
        # bernoulli に lru_cache を使うと O(k**2 * log(mod))  bernoulli が計算済みなら O(k * log(mod))
        return pow(k+1, self.mod-2, self.mod) * sum(self.C(k+1, j) * self.bernoulli(j) % self.mod * pow(n, k-j+1, self.mod) % self.mod for j in range(k+1)) % self.mod

    def lah(self, n, k):  # n 要素を k 個の空でない順序付き集合に分割する場合の数  O(1)
        return self.C(n-1, k-1) * self.fac[n] % self.mod * self.facinv[k] % self.mod

    def bell(self, n, k):  # n 要素を k 個以下に分割する場合の数  O(k**2 + k*log(mod))
        return sum(self.stirling_second(n, j) for j in range(1, k+1)) % self.mod

mod = 10**9+7
comb = Combination(2000)
n, k = map(int, input().split())
print(comb.balls_and_boxes_3(n, k))

Submission status: Accepted

Solution code:
n, k = map(int, input().split( ))
mod = 10**9+7

def chs(s,t,mod):
    nume =  1
    for i in range(s-t+1,s+1):
        nume *= i
        nume %= mod
    deno = 1
    for i in range(1,t+1):
        deno *= i
        deno %= mod
    deno = pow(deno,mod-2,mod)
    
    return (nume*deno%mod)
ans = 0

for i in range(k):
    x1 = chs(k, k-i, mod)
    #print("chs",x1)
    x2 = pow(k-i,n, mod)
    #print("pow",x2)
    ans += x1*x2*(-1)**i
print(ans%mod)

Submission status: Accepted

Solution code:
import math


def combination(i: int, j: int) -> int:
    return math.factorial(i) // math.factorial(i - j) // math.factorial(j)


if __name__ == "__main__":
    n, k = map(lambda x: int(x), input().split())
    modulo = 10 ** 9 + 7
    ans = 0
    if k <= n:
        for i in range(k):
            if 0 == i % 2:
                ans += (k - i) ** n * combination(k, i)
            else:
                ans -= (k - i) ** n * combination(k, i)
        ans = ans % modulo

    print(ans)

Submission status: Accepted

Solution code:
import math
def comb(n, k):
    if n < 0 or k < 0 or n < k: return 0
    return math.factorial(n) // math.factorial(n-k) // math.factorial(k)



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

all = 0

for i in range(k):
    add = comb(k, i) * ((k-i) ** n) % MOD
    if i & 1: all = (all - add + MOD) % MOD
    else: all = (all + add) % MOD

print(all)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
MOD = 10**9 + 7
 
if N < K:
    print(0)
else:
    ans = 0
    v = 1
    for i in range(K):
        if i % 2:
            ans -= pow(K-i, N, MOD) * v
        else:
            ans += pow(K-i, N, MOD) * v
        v = v * (K-i) * pow(i+1, MOD-2, MOD) % MOD
    print(ans % MOD)

Submission status: Accepted

Solution code:
from collections import defaultdict
    
class Combinatorics:
    def __init__(self, N, mod):
        '''
        Preprocess for calculating binomial coefficients nCr (0 <= r <= n, 0 <= n <= N)
        over the finite field Z/(mod)Z.
        Input:
            N (int): maximum n
            mod (int): a prime number. The order of the field Z/(mod)Z over which nCr is calculated.
        '''
        self.mod = mod
        self.fact = {i: None for i in range(N+1)}         # n!
        self.inverse = {i: None for i in range(1, N+1)}   # inverse of n in the field Z/(MOD)Z
        self.fact_inverse = {i: None for i in range(N+1)} # inverse of n! in the field Z/(MOD)Z
        
        # preprocess
        self.fact[0] = self.fact[1] = 1
        self.fact_inverse[0] = self.fact_inverse[1] = 1
        self.inverse[1] = 1
        for i in range(2, N+1):
            self.fact[i] = i * self.fact[i-1] % self.mod
            q, r = divmod(self.mod, i)
            self.inverse[i] = (- (q % self.mod) * self.inverse[r]) % self.mod
            self.fact_inverse[i] = self.inverse[i] * self.fact_inverse[i-1] % self.mod
    
    def perm(self, n, r):
        '''
        Calculate nPr = n! / (n-r)! % mod
        '''
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return (self.fact[n] * self.fact_inverse[n-r]) % self.mod
    
    def binom(self, n, r):
        '''
        Calculate nCr = n! /(r! (n-r)!) % mod
        '''
        if n < r or n < 0 or r < 0:
            return 0
        else:
            return self.fact[n] * (self.fact_inverse[r] * self.fact_inverse[n-r] % self.mod) % self.mod
        
    def hom(self, n, r):
        '''
        Calculate nHr = {n+r-1}Cr % mod.
        Assign r objects to one of n classes.
        Arrangement of r circles and n-1 partitions:
            o o o | o o | | | o | | | o o | | o
        '''
        if n == 0 and r > 0:
            return 0
        if n >= 0 and r == 0:
            return 1
        return self.binom(n + r - 1, r)
    
n, k = map(int, input().split())
MOD = 10**9 + 7
com = Combinatorics(k, MOD)
ans = 0
for i in range(k):
    if i % 2 == 0:
        ans = (ans + com.binom(k, i) * pow(k - i, n, MOD)) % MOD
    else:
        ans = (ans - com.binom(k, i) * pow(k - i, n, MOD)) % MOD
print(ans)

Submission status: Accepted

Solution code:
from math import factorial
def P(n,r):
    return factorial(n)//factorial(n-r)
def C(n,r):
    return P(n,r)//factorial(r)
def calc(n,k):
    ans = 0
    for i in range(k):
        ans += (k-i)**n*C(k,i)*(-1)**i
    return ans
n, k = map(int, input().split())
print(calc(n,k)%(pow(10,9)+7) if n > k else factorial(n)%(pow(10,9)+7) if n == k else 0 )

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#1:combinatorial
#1_A
"""
n, m = map(int, input().split())
c = list(map(int, input().split()))
dp = [float("inf") for i in range(n+1)]
dp[0] = 0
for i in range(n):
    for j in c:
        if i+j <= n:
            dp[i+j] = min(dp[i+j], dp[i]+1)
print(dp[n])
"""
#1_B
"""
n,w = map(int,input().split())
b = [list(map(int, input().split())) for i in range(n)]
dp = [0 for i in range(w+1)]
memo = [[] for i in range(w+1)]
for i in range(w):
    for j in range(n):
        if i+b[j][1] <= w and j not in memo[i]:
            if dp[i+b[j][1]] > dp[i]+b[j][0]:
                continue
            else:
                memo[i+b[j][1]] = memo[i]+[j]
                dp[i+b[j][1]] = dp[i]+b[j][0]

print(max(dp))
"""
#1_C
"""
n,w = map(int,input().split())
b = [list(map(int, input().split())) for i in range(n)]
dp = [0 for i in range(w+1)]
for i in range(w):
    for j in b:
        if i+j[1] <= w:
            dp[i+j[1]] = max(dp[i+j[1]], dp[i]+j[0])
print(dp[w])
"""
#1_D
"""
import bisect

n = int(input())
s = [int(input()) for i in range(n)]
dp = [float("INF") for i in range(n)]
for i in range(n):
    dp[bisect.bisect_left(dp,s[i])] = s[i]
print(bisect.bisect_left(dp,100000000000000))
"""

#1_E
"""
s1 = input()
s2 = input()
n = len(s1)
m = len(s2)
dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = i
for j in range(m+1):
    dp[0][j] = j
for i in range(1,n+1):
    for j in range(1,m+1):
        cost = 0 if s1[i-1] == s2[j-1] else 1
        dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+cost)
print(dp[n][m])
"""
#1_F
"""
import bisect

n,W = map(int,input().split())
b = [list(map(int, input().split())) for i in range(n)]
dp = [float("INF") for i in range(10001)]
dp[0] = 0
for v,w in b:
    for i in range(10001):
        if 10000-i+v < 10001:
            dp[10000-i+v] = min(dp[10000-i+v], dp[10000-i]+w)
for i in range(1,10000):
    dp[10000-i] = min(dp[10000-i], dp[10001-i])
print(bisect.bisect_right(dp,W)-1)
"""

#1_G
"""
n,W = LI()
g = LIR(n)
"""

#1_H


#2:permutaion/path
#2_A
"""
n,e = LI()
v = [[] for i in range(n)]
f = [-1 for i in range(n)]
for i in range(e):
    s,t,d = LI()
    v[s].append([t,d])
    if t == 0:
        f[s] = d
po = [1 for i in range(n+1)]
for i in range(n):
    po[i+1] = po[i]*2
dp = [[float("inf") for i in range(po[n])] for j in range(n)]
dp[0][1] = 0
for j in range(po[n]):
    for x in range(n):
        if po[x]&j:
            for y,d in v[x]:
                if not po[y]&j:
                    dp[y][j|po[y]] = min(dp[y][j|po[y]],dp[x][j]+d)
ans = float("inf")
for i in range(n):
    if f[i] != -1:
        ans = min(ans,dp[i][-1]+f[i])
if ans == float("inf"):
    print(-1)
else:
    print(ans)
"""
#3:pattern

#3_A
"""
h,w = map(int, input().split())
c = [list(map(int, input().split())) for i in range(h)]
dp = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    dp[i][0] = 1 if c[i][0] == 0 else 0
for i in range(w):
    dp[0][i] = 1 if c[0][i] == 0 else 0
for i in range(1,h):
    for j in range(1,w):
        if c[i][j] == 0:
            dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1
ans = 0
for i in dp:
    for j in i:
        ans = max(ans, j)
print(ans**2)
"""

#3_B

#4:counting
#4_A
"""
n,v = LI()
a = LI()
b = LI()
c = LI()
d = LI()
p = defaultdict(int)
q = defaultdict(int)
for i in a:
    for j in b:
        if i+j <= v-2:
            p[i+j] += 1
for i in c:
    for j in d:
        if i+j <= v-2:
            q[i+j] += 1
ans = 0
for i,j in p.items():
    ans += j*q[v-i]
print(ans)
"""


#5:Twelvedfold_Way

#5_A
"""
n,k = map(int, input().split())
ans = k
for i in range(n-1):
    ans *= k
    ans %= 1000000007
print(ans)
"""

#5_B
"""
import sys
sys.setrecursionlimit(10000)
memo = [1,1]
def fact(a):
    if len(memo) > a:
        return memo[a]
    b = a*fact(a-1)
    memo.append(b)
    return b
n,k = map(int, input().split())
if n > k:
    ans = 0
else:
    ans = fact(k)//fact(k-n)
print(ans%1000000007)
"""

#5_C
def comb(a,b):
    return fac[a]*inv[b]*inv[a-b]%mod
n,k = LI()
if n < k:
    print(0)
    quit()
fac = [1 for i in range(k+1)]
for i in range(k):
    fac[i+1] = fac[i]*(i+1)%mod
inv = [None for i in range(n+1)]
inv[k] = pow(fac[k],mod-2,mod)
for i in range(k)[::-1]:
    inv[i] = inv[i+1]*(i+1)%mod
ans = 0
for i in range(k+1):
    if i%2:
        ans -= comb(k,i)*pow(k-i,n,mod)%mod
    else:
        ans += comb(k,i)*pow(k-i,n,mod)%mod
    ans %= mod
print(ans)
#5_D
"""
n,k = map(int, input().split())
import sys
sys.setrecursionlimit(10000)
memo = [1,1]
def fact(a):
    if len(memo) > a:
        return memo[a]
    b = a*fact(a-1)
    memo.append(b)
    return b
ans = fact(n+k-1)//(fact(n)*fact(k-1))%1000000007
print(ans)
"""

#5_E
"""
import sys
sys.setrecursionlimit(10000)
memo = [1,1]
def fact(a):
    if len(memo) > a:
        return memo[a]
    b = a*fact(a-1)
    memo.append(b)
    return b
n,k = map(int, input().split())
ans = fact(n+k-1)//(fact(n)*fact(k-1))%1000000007
print(ans)
"""
#5_F

#5_G

#5_H

#5_I

#5_J

#5_K

#5_L