Problem:
Balls and Boxes 9  Balls Boxes Any way At most one ball At least one ball  Distinguishable Distinguishable 1 2 3  Indistinguishable Distinguishable 4 5 6  Distinguishable Indistinguishable 7 8 9  Indistinguishable Indistinguishable 10 11 12  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 not 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 6 Sample Input 2 10 5 Sample Output 2 42525 Sample Input 3 100 30 Sample Output 3 203169470

Solution (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())

m_comb = {}
m_pow = {}
m_inv = {}

def comb(N, K):
    if (N, K) in m_comb:
        return m_comb[(N, K)]
    if N == K or K == 0:
        m_comb[(N, K)] = 1
        return 1
    m_comb[(N, K)] = (comb(N - 1, K) + comb(N - 1, K - 1)) % MOD
    return m_comb[(N, K)]

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

def inv(N):
    if N in m_inv:
        return m_inv[N]
    pow_num = MOD - 2
    pow_cur = N
    ret = 1
    while pow_num > 0:
        if pow_num % 2 == 1:
            ret *= pow_cur
            ret %= MOD
        pow_cur *= pow_cur
        pow_cur %= MOD
        pow_num /= 2
    m_inv[N] = ret
    return ret

ans = pow(k)
sig = -1

for i in range(k - 1, 0, -1):
    ans += (comb(k, i) * pow(i) % MOD) * sig
    sig *= -1

for i in range(1, k + 1):
    ans *= inv(i)
    ans %= MOD

print ans

Solution (Python):
class Twelvefold(): 
    def __init__(self, n, mod, build=True):
        self.mod = mod
        self.fct = [0 for _ in range(n + 1)]
        self.inv = [0 for _ in range(n + 1)]
        self.fct[0] = 1
        self.inv[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
        if build: self.build(n)

    def build(self, n):
        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.stl[0][0] = 1
        self.bel[0][0] = 1
        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] %= self.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] % self.mod
                self.bel[i + 1][j + 1] %= self.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] %= self.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] % self.mod

    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, 1)
print(t.solve(n, k, 0, 1, 0, 1))

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

if N<K:
    print(0)
    exit()

D = [[0]*(K+1) for i in range(N+1)]
D[0][0] = 1


for n in range(1, N+1):
    D0 = D[n-1]
    
    for k in range(1, K+1):
        
        
        
        D[n][k] = (D0[k-1] + k * D0[k]) % MOD
print(D[N][K] % MOD)

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,r = map(int,readline().split())
mod = 10**9+7



def pow(n,p,mod=mod): 
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def factrial_memo(n=10**5,mod=mod):
    fact = [1, 1]
    for i in range(2, n + 1):
        fact.append((fact[-1] * i) % mod)
    return fact

fact = factrial_memo()

def permutation(n,r): 
    return fact[n]*pow(fact[n-r],mod-2)%mod
def combination(n,r): 
    return permutation(n,r)*pow(fact[r],mod-2)%mod
    
def homogeneous(n,r): 
    return combination(n+r-1,r)%mod
    

def stirling(n,r): 
    res = 0
    for i in range(r): 
        res += pow(-1,i)*combination(r,i)*pow(r-i,n)
        res %= mod
    for i in range(1,r+1): 
        res *= pow(i,mod-2)%mod
        res %= mod
    return res

print(stirling(n,r))

Solution (Python):
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 resolve():
    n, k = LI()

    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 1

    for i in range(n):
        for j in range(k):
            dp[i+1][j+1] = dp[i][j] + (j + 1) * dp[i][j+1]
            dp[i+1][j+1] %= MOD

    print(dp[-1][-1])

if __name__ == '__main__':
    resolve()

Solution (Python):
N, K = map(int, input().split())
mod = 10 ** 9 + 7
S = [[0] * (K + 1) for i in range(N + 1)]
S[0][0] = 1
for n in range(1, N + 1):
	for k in range(1, K + 1):
		S[n][k] = (S[n - 1][k - 1] + k * S[n - 1][k]) % mod
print(S[N][K])

Solution (Python):
def way9(ball, box):
    """ball: True / box: False / constraints: 1 or more
    -> ans = S(ball, box)  Sはスターリング数 / 計算量 O(ball * box)
    """
    if ball < box:
        return 0

    
    S = [[0] * (box + 1) for i in range(ball + 1)] 
    S[0][0] = 1
    for i in range(ball):
        for j in range(box):
            S[i + 1][j + 1] = S[i][j] + S[i][j + 1] * (j + 1)
            S[i + 1][j + 1] %= MOD

    return S[ball][box]


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

print(way9(n, k))

Solution (Python):
mod = 10**9 + 7
stering = [[-1]*1001 for _ in range(1001)]
for i in range(1001):
    stering[i][1] = 1
    stering[i][i] = 1

def roop(n, k):
    if stering[n][k] != -1:
        return stering[n][k]
    else:
        stering[n][k] = (roop(n-1, k-1) + k * roop(n-1, k)) % mod
        return stering[n][k]

n, k = [int(s) for s in input().split()]
if n < k:
    print(0)
else:
    ans = roop(n, k)
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

mod = 10**9 + 7
star = [[None] * 1001 for _ in range(1001)]

for i in range(1001):
    star[i][i] = 1
    star[i][1] = 1

def search(n, k):
    if star[n][k]:
        return star[n][k] % mod
    else:
        star[n][k] = (search(n-1, k-1) + k * search(n-1, k)) % mod
        return star[n][k]

n, k = map(int, input().split())
if n < k:
    print(0)
else:
    print(search(n,k))

Solution (Python):
import sys
sys.setrecursionlimit(10**4)

n, k = map(int, input().split())
stirling = [[-1 for _ in range(k+1)] for _ in range(n+1)]

MOD = 10**9 + 7

def rec(nn, kk):
    if nn < kk:
        return 0
    if kk == 1 or kk == nn:
        return 1
    if stirling[nn][kk] == -1:
        stirling[nn][kk] = (kk * rec(nn-1, kk) + rec(nn-1, kk-1)) % MOD
    return stirling[nn][kk]

print(rec(n, k))

Solution (Python):


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

def resolve():
    N, K = iim()
    mod = 10**9 + 7

    dp = [[0]*(K+1) for i in range(2)]

    dp0, dp1 = dp
    dp0[0] = 1
    for i in range(1, N+1):
        for j in range(1, K+1):
            dp1[j] = (dp0[j-1] + dp0[j]*j) % mod
        dp1[0] = 0
        dp0, dp1 = dp1, dp0
    print(dp0[K] % mod)
if __name__ == "__main__":
    resolve()

Solution (Python):
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]

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

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

print((f(n,k)//facts[k])%mod)

Solution (Python):
class Combination:
    def __init__(self, n_max, mod=10**9+7):
        
        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):  
        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) or 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):  
        return self.fac[n+r-1] * self.facinv[n-1] % self.mod

    def stirling_first(self, 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):  
        if n == k: return 1  
        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):  
        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):  
        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):  
        
        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):  
        return self.C(n-1, k-1) * self.fac[n] % self.mod * self.facinv[k] % self.mod

    def bell(self, n, k):  
        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.stirling_second(n, k))

Solution (Python):
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 // math.factorial(k)) % modulo

    print(ans)

Solution (Python):
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)
    if i & 1: all = (all - add)
    else: all = (all + add)

print(all // (math.factorial(k)) % MOD)

Solution (Python):
N, K = map(int, input().split())
MOD = 10**9 + 7
 
D = [[0]*(K+1) for i in range(N+1)]
D[0][0] = 1
for n in range(1, N+1):
    D0 = D[n-1]
    for k in range(1, K+1):
        D[n][k] = (D0[k-1] + k * D0[k]) % MOD
print(D[N][K])

Solution (Python):
from collections import defaultdict

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

def Stirling_second(n, k, mod):
    Stir = {i: defaultdict(int) for i in range(n + 1)}
    Stir[1][1] = 1
    for i in range(2, n+1):
        Stir[i][1] = 1
        for j in range(2, k+1):
            Stir[i][j] = (Stir[i-1][j-1] + (j * Stir[i-1][j]) % mod) % mod
    return Stir
s = Stirling_second(N, K, MOD)
ans = s[N][K]
print(ans)

Solution (Python):

N, K = map(int, input().split())
MOD = 10**9 + 7
N = N 
D = [[0]*(K+1) for i in range(N+1)]
D[0][0] = 1
for n in range(1, N+1):
    for k in range(1, K+1):
        D[n][k] = (D[n-1][k-1]+k*D[n-1][k]) % MOD
print(D[N][-1])

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

D = [[0]*(K+1) for i in range(N+1)]
D[0][0] = 1
for n in range(1, N+1):
    D0 = D[n-1]
    for k in range(1, K+1):
        D[n][k] = (D0[k-1] + k * D0[k]) % MOD
print(D[N][K])

Solution (Python):
n,k=map(int,input().split(" "))
if n<k:
    print(0)
else:
    a=[1,0]
    for i in range(n):
        a=[0]+[a[i-1]+i*a[i] for i in range(1,len(a))]+[0]
    print(a[k]%(10**9+7))