Problem:


Balls and Boxes 7

  
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 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



Sample input:
3 5


Sample output:
5

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# 文字列の入力
import math

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

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
    

mod = 10**9+7 #出力の制限
N = 10**4
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 )
ans = 0

for i in range(1,n+1):
    ansb = 0
    for j in range(1, i+1):
        ansb += ((-1)**(i-j))*cmb(i, j, mod)*(j**n)
    ansb /= math.factorial(i)
    ans += ansb 
print(int(ans))

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

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

Submission status: Accepted

Solution code:
class Twelvefold(): #n <= 1000程度
    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))

Submission status: Accepted

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

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

# nはn個のボールをいれるのを1から順番に考える
for n in range(1, N+1):
    D0 = D[n-1]
    # kはkこの箱にnこれいた場合の数
    for k in range(1, K+1):
        # 前回D[n-1][k-1]はk-1個の箱にn-1個入れてるので、それにn個めを新しい箱に入れるとD0[k-1]を足すことになる
        # 前回D[n-1][k-1]はk-1個の箱にn-1個入れてて、それぞれにn個めを1個足してくとそのパターンはk*D0[k]個ある
        # 頭ヨ
        D[n][k] = (D0[k-1] + k * D0[k]) % MOD
print(sum(D[N]) % MOD)

Submission status: Accepted

Solution code:
#balls and boxes 7
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): # [1,n)までの階乗と逆元の階乗
    fact = [1, 1]  # fact[n] = (n! mod mod)
    factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod mod)
    inv = [0, 1]  # factinv 計算用
    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 # warning:1-indexed list

fact,factinv = factrial_memo()

#ベル数O(k)
def bell(n,r): #nBr
    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))

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
def way7(ball, box):
    """ball: True / box: False / constraints: None
    -> ans = B(ball, box)  Bはベル数 / 計算量 O(ball * box)
    """
    # B[i][j] := S[i][j] + S[i][j - 1] + ... + S[i][0]
    # S[i][j] := i個(区別する)をkグループ(区別しない)に分ける場合の数
    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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!python3

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

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
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)

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) 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):  # 上昇階乗冪 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.bell(n, k))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

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)

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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))