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:
import sys
sys.setrecursionlimit(1000000)
memo = {0:1}
def fact(x):
  if x in memo:
    return memo[x]
  memo[x] = x * fact(x - 1)
  return memo[x]

def comb(x, y):
  return fact(x) // fact(x - y) // fact(y)

n, k = map(int, input().split())
if n < k:print(0)
else:
  ans = 0
  for i in range(k):
    #print(ans)
    ans += (k - i) ** n * comb(k, i) * (-1) ** i
  print(ans % 1000000007)

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:
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]
    for i in range(1,k+1):
        a[k]*=i
    print(a[k]%(10**9+7))