Problem:
Balls and Boxes 7  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 can contain an arbitrary number of balls (including zero).  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 3 5 Sample Output 1 5 Sample Input 2 5 3 Sample Output 2 41 Sample Input 3 100 100 Sample Output 3 193120002

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 = 0
for k in range(1, k_ + 1):
    num = pow(k)
    sig = -1

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

    for i in range(1, k + 1):
        num *= inv(i)
        num %= MOD
    ans += num
    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, 0))

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(sum(D[N]) % MOD)

Solution (Python):

import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,k = 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]  
    factinv = [1, 1]  
    inv = [0, 1]  
    for i in range(2, n + 1):
        fact.append((fact[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * inv[-1]) % mod)
    return fact,factinv 

fact,factinv = factrial_memo()


def bell(n,r): 
    if r > n:r = n

    memo = [0]*(r+2)
    for i in range(r+1):
        if even(i):memo[i+1] = memo[i] + factinv[i]
        else:memo[i+1] = memo[i] - factinv[i]
    res = 0
    for i in range(r+1):
        res += pow(i,n)*factinv[i]*memo[r-i+1]%mod
        res %= mod
    return res

print(bell(n,k))

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

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

    print(ans)

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(sum(S[N][:K+1])%mod)

Solution (Python):
def way7(ball, box):
    """ball: True / box: False / constraints: None
    -> ans = B(ball, box)  Bはベル数 / 計算量 O(ball * box)
    """
    
    
    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

    B_ij = sum(S[ball][0:box + 1]) % MOD
    return B_ij


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

print(way7(n, k))

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][1] = 1
    star[i][i] = 1
    star[i][0] = 0

def search(n, k):
    if n < k:
        return 0
    elif star[n][k] != None:
        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())
ans = 0
for i in range(k+1):
    ans += search(n, i)
    ans = ans % mod

print(ans)

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


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

def roop(n, k):
    if n < k:
        return 0
    else:
        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()]
ans = 0
for i in range(k+1):
    ans += roop(n, i)

print(ans % mod)

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 or kk == 0:
        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(sum(rec(n, kk) for kk in range(k+1)) % MOD)

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(N+1)]
    dp[0][0] = 1
    for i in range(1, N+1):
        dd = dp[i]
        for k in range(1, K+1):
            dp[i][k] = dp[i-1][k-1] + k * dp[i-1][k]
            dp[i][k] %= mod

    

    print(sum(dp[N]) % mod)

if __name__ == "__main__":
    resolve()

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


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

for i in range(1,n+1):
    for j in range(1,k+1):
        if i<j:
            tables[i][j]=0
        elif j==1:
            tables[i][j]=1

        elif i==j:
            tables[i][j]=facts[i]

        else:
            tables[i][j]=j*(tables[i-1][j]+tables[i-1][j-1])

def f(n,k):
    if n<k:
        return 0
    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

retval=0
for i in range(1,k+1):
    retval+=(tables[n][i]//facts[i])%mod

print(retval%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.bell(n, k))

Solution (Python):
if __name__ == "__main__":
    n, k = map(lambda x: int(x), input().split())
    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(sum(a[:k + 1]) % (10 ** 9 + 7))

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(sum(D[N]) % MOD)

Solution (Python):
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)}         
        self.inverse = {i: None for i in range(1, N+1)}   
        self.fact_inverse = {i: None for i in range(N+1)} 
         
        
        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)

def Bell_num(n, k, mod):
    com = Combinatorics(k, mod)
    temp = [1]
    for i in range(1, k+1):
        temp.append((temp[-1] + ((-1)**i * com.fact_inverse[i]) % mod) % mod)
    ans = 0
    for i in range(k+1):
        ans = (ans + (((pow(i, n, mod) * com.fact_inverse[i]) % mod)* temp[k-i]) % mod) % mod
    return ans
    
N, K = map(int, input().split())
MOD = 10**9 + 7
ans = Bell_num(N, K, MOD)
print(ans)

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):
    for k in range(1, K+1):
        D[n][k] = (D[n-1][k-1]+k*D[n-1][k]) % MOD
print(sum(D[N])%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(sum(D[N]) % MOD)

Solution (Python):
n,k=map(int,input().split(" "))
k=min(n,k)
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(sum(a[:k+1])%(10**9+7))