A permutation p of size n is an array such that every integer from 1 to n occurs exactly once in this array.

Let's call a permutation an almost identity permutation iff there exist at least n - k indices i (1 ≤ i ≤ n) such that p_{i} = i.

Your task is to count the number of almost identity permutations for given numbers n and k.


-----Input-----

The first line contains two integers n and k (4 ≤ n ≤ 1000, 1 ≤ k ≤ 4).


-----Output-----

Print the number of almost identity permutations for given n and k.


-----Examples-----
Input
4 1

Output
1

Input
4 2

Output
7

Input
5 3

Output
31

Input
5 4

Output
76

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Combinatorics

Mathematics


Solutions:
import math

def calculate_derangement(fac, n):
	ans = fac[n]
	for i in range(1, n + 1):
		if i % 2 == 1:
			ans -= fac[n] // fac[i]
		else:
			ans += fac[n] // fac[i]
	return ans
(n, k) = map(int, input().split())
fac = [1]
for i in range(1, n + 1):
	fac.append(fac[i - 1] * i)
ans = 0
for i in range(0, k + 1):
	choose = fac[n]
	choose //= fac[i]
	choose //= fac[n - i]
	ans += choose * calculate_derangement(fac, i)
print(ans)


(n, k) = map(int, input().split())
dg = [0, 0, 1, 2, 9]

def getCombinationValue(r):
	if r == 0:
		return 1
	elif r == 1:
		return n
	elif r == 2:
		return (n - 1) * n // 2
	elif r == 3:
		return (n - 1) * n * (n - 2) // 6
	elif r == 4:
		return (n - 1) * n * (n - 2) * (n - 3) // 24
ans = 1
for m in range(k + 1):
	ans += getCombinationValue(m) * dg[m]
print(ans)


import math
(n, k) = map(int, input().split())
dp = [1, n * (n - 1) // 2, n * (n - 1) * (n - 2) * 2 // 6, n * (n - 1) * (n - 2) * (n - 3) * 9 // 24]
ans = 0
for i in range(0, k):
	ans += dp[i]
print(ans)


def countDer(n):
	der = [0 for i in range(max(3, n + 1))]
	der[0] = 1
	der[1] = 0
	der[2] = 1
	for i in range(3, n + 1):
		der[i] = (i - 1) * (der[i - 1] + der[i - 2])
	return der[n]

def nCr(n, r):
	return fact(n) / (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res
(n, k) = map(int, input().split())
j = n - k
s = 0
while j <= n:
	s += nCr(n, j) * countDer(n - j)
	j += 1
print(int(s))


from functools import reduce
_ = "\n (1) Let's define function f(n, k) - exactly k permutation elements\n     on non identical indices.\n     Our result function is then: F(n, k) = sum(f(n, ki) ki = 0 .. k)\n \n (2) f(n, 0) = 1\n     f(n, 1) = 0\n \n (3) We choose k indices - C(n, k).\n     All other indices are fixed and identical.\n     We need to permutate k! elements\n     so we do not set them to their own identical positions.\n     Let's define the latter function as ni(k)\n \n (4) ni(0) = 1\n     ni(1) = 0\n     ni(2) = 1\n     ni(3) = 2\n     0 1 2 - doesn't count\n     0 2 1 - doesn't count\n     1 0 2 - doesn't count\n     1 2 0\n     2 0 1\n     2 1 0 - doesn't count\n \n (5) We choose (k-1) elements for first position.\n     Let's define chosen element c1\n     Then we go to c1 position. There we can choose from (k-1) elements (c2).\n     Then we go to c2 position. There we can choose from (k-2) elements (c3).\n     Then we go to c3 position. There we can choose from (k-3) elements (c4).\n     ni'(k) := (k-1)*(k-1)!\n \n     ni'(2) := (2-1)*(2-1)! = 1\n     ni'(3) := (3-1)*(3-1)! = 4 - WRONG\n \n Let's just brutforce h(n, k) or manually check the last k=4 answer.\n"
ni = [1, 0, 1, 2, 9]
(n, k) = map(int, input().split())

def f_exactly_k(n, k):
	return reduce(lambda x, y: x * y, range(n - k + 1, n + 1), 1) // reduce(lambda x, y: x * y, range(1, k + 1), 1) * ni[k]
s = 0
for ki in range(k + 1):
	s += f_exactly_k(n, ki)
print(s)


import sys
import math
import operator as op
from functools import reduce
from sys import maxsize

def read_line():
	return sys.stdin.readline()[:-1]

def read_int():
	return int(sys.stdin.readline())

def read_int_line():
	return [int(v) for v in sys.stdin.readline().split()]

def read_float_line():
	return [float(v) for v in sys.stdin.readline().split()]

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer / denom

def nc2(n):
	return n * (n - 1) // 2
t = 1
for i in range(t):
	(n, k) = read_int_line()
	dp = [0] * (n + 1)
	dp[0] = 1
	dp[1] = 0
	dp[2] = 1
	for i in range(3, n + 1):
		dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])
	ans = 0
	for i in range(k + 1):
		ans += ncr(n, i) * dp[i]
	print(int(ans))


(n, k) = map(int, input().split())
o = 1
if k > 1:
	o += n * (n - 1) // 2
if k > 2:
	o += n * (n - 1) * (n - 2) // 3
if k > 3:
	o += n * (n - 1) * (n - 2) * (n - 3) // 8 * 3
print(o)


(n, k) = map(int, input().split())
ans = 1
k = min(k, n)
if k == 1:
	print(1)
elif k == 2:
	ans += n * (n - 1) // 2
	print(ans)
elif k == 3:
	ans += n * (n - 1) * (n - 2) // 3 + n * (n - 1) // 2
	print(ans)
else:
	ans += n * (n - 1) * (n - 2) * (n - 3) // 4 + n * (n - 1) * (n - 2) * (n - 3) // 8 + n * (n - 1) * (n - 2) // 3 + n * (n - 1) // 2
	print(ans)


(n, k) = [int(i) for i in input().split()]
ans = 1
if k >= 2:
	ans += n * (n - 1) // 2
if k >= 3:
	ans += n * (n - 1) * (n - 2) // 6 * 2
if k >= 4:
	ans += n * (n - 1) * (n - 2) * (n - 3) // 24 * 9
print(ans)


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
(N, K) = list(map(int, input().split()))
if K == 1:
	print(1)
elif K == 2:
	print(1 + N * (N - 1) // 2)
elif K == 3:
	print(1 + N * (N - 1) // 2 + N * (N - 1) * (N - 2) // 3)
elif K == 4:
	print(1 + N * (N - 1) // 2 + N * (N - 1) * (N - 2) // 3 + 3 * N * (N - 1) * (N - 2) * (N - 3) // 8)


from math import factorial as f
(n, k) = map(int, input().split())
dp = [1, 0]
ans = 1
for i in range(2, k + 1):
	dp.append((i - 1) * (dp[-1] + dp[-2]))
	ans += f(n) // f(i) // f(n - i) * dp[i]
print(ans)


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz/'
M = 1000000007
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]

def nCr(n, r):
	(p, k) = (1, 1)
	r = min(n - r, r)
	if r != 0:
		while r:
			p *= n
			k *= r
			m = gcd(p, k)
			p //= m
			k //= m
			n -= 1
			r -= 1
	else:
		p = 1
	return p
(n, k) = value()
C = {0: 1, 1: 0, 2: 1, 3: 2, 4: 9}
ans = 0
for i in range(k + 1):
	ans += nCr(n, i) * C[i]
print(ans)


(n, k) = map(int, input().split())
sum = 0
if k >= 0:
	sum += 1
if k >= 2:
	pres = n * (n - 1) / 2
	sum += pres
if k >= 3:
	pres = n * (n - 1) * (n - 2) / 6
	sum += pres * 2
if k >= 4:
	pres = n * (n - 1) * (n - 2) * (n - 3) / 24
	sum += pres * (3 * 3)
print(int(sum))


(n, k) = map(int, input().split())
dp = [[[0] * (k + 1) for i in range(n + 1)] for j in range(k + 1)]
dp_c = [[[0] * (k + 1) for i in range(n + 1)] for j in range(k + 1)]
for i in range(1, n):
	dp[1][i][1] = 1
store = [0, 1, 1, 2, 9]
ans = 0
for i in range(2, k + 1):
	add = 0
	for j in range(1, n + 1):
		add += dp[i - 1][j - 1][i - 1]
		if j >= i:
			dp[i][j][i] = add
			dp_c[i][j][i] = add * store[i]
			ans += dp_c[i][j][i]
print(ans + 1)


(N, K) = map(int, input().split())
print(sum([1, 0, N * (N - 1) // 2, N * (N - 1) * (N - 2) // 3, N * (N - 1) * (N - 2) * (N - 3) * 3 // 8][:K + 1]))


(n, k) = map(int, input().split())
res = 1
if k >= 2:
	res += n * (n - 1) / 2
if k >= 3:
	res += n * (n - 1) * (n - 2) / 3
if k >= 4:
	res += n * (n - 1) * (n - 2) * (n - 3) / 24 * 9
print(int(res))


import sys, math, queue, bisect
MOD = 10 ** 9 + 7
sys.setrecursionlimit(1000000)
(n, k) = map(int, input().split())
if k == 1:
	print(1)
elif k == 2:
	ans = 1 + n * (n - 1) // 2
	print(ans)
elif k == 3:
	ans = 1 + n * (n - 1) // 2 + n * (n - 1) * (n - 2) // 3
	print(ans)
else:
	ans = 1 + n * (n - 1) // 2 + n * (n - 1) * (n - 2) // 3 + 9 * (n * (n - 1) * (n - 2) * (n - 3) // 24)
	print(ans)


d = input()
n = int(d.split(' ')[0])
k = int(d.split(' ')[1])

def c(a, b):
	s = 1
	for i in range(b):
		s *= a - i
		s /= i + 1
	return int(s)
dizi = [-1, 0, 1, 2, 9]
son = 0
for i in range(k, 1, -1):
	son += c(n, i) * dizi[i]
print(son + 1)


import sys
(sn, sk) = sys.stdin.readline().split()
(n, k) = (int(sn), int(sk))
ret = [0, 0, 0, 0, 0]
ret[0] = 1
ret[1] = 1 + int(n * (n - 1) // 2)
ret[2] = ret[1] + int(n * (n - 1) * (n - 2) // 3)
ret[3] = ret[2] + int(3 * n * (n - 1) * (n - 2) * (n - 3) // 8)
ret[4] = ret[3] + int(11 * n * (n - 1) * (n - 2) * (n - 3) * (n - 4) // 30)
print(ret[k - 1])


(n, k) = map(int, input().split())
p = [0, 1, 1, 2, 9]
f = [0, 1, 2, 6, 24]
ans = 0
for i in range(n - k, n - 1):
	m = 1
	for j in range(i + 1, n + 1):
		m *= j
	add = m // f[n - i] * p[n - i]
	ans += add
print(ans + 1)


a = [0, 0, 1, 2, 9]

def C(n, k):
	if n == 0 or k > n:
		return 0
	k = max(k, n - k)
	lim = min(k, n - k)
	ret = 1
	j = 2
	for i in range(k + 1, n + 1):
		ret = ret * i
		if j <= lim and ret % j == 0:
			ret /= j
			j += 1
	return ret
(n, k) = map(int, input().split())
ans = 0
for i in range(1, k + 1):
	ans += a[i] * C(n, i)
print(int(ans + 1))


from math import factorial as f

def cnk(n, k):
	x = int(f(n) // (f(k) * f(n - k)))
	return x
(n, k) = map(int, input().split())
acc = 0
if k >= 1:
	acc += 1
if k >= 2:
	acc += cnk(n, 2)
if k >= 3:
	acc += cnk(n, 3) * 2
if k == 4:
	acc += cnk(n, 4) * 9
print(acc)


def notinx(x):
	if x == 0:
		return 1
	if x == 1:
		return 0
	fac = [1]
	for i in range(x):
		fac.append(fac[-1] * (i + 1))
	ans = 0
	for i in range(x):
		ans += fac[x] / fac[i + 1] * pow(-1, i)
	ans = fac[x] - ans
	return ans

def nCr(n, r):
	(up, down) = (1, 1)
	for i in range(r):
		down *= i + 1
		up *= n - i
	return up / down

def solve(n, k):
	ans = 0
	for i in range(k + 1):
		ans += nCr(n, i) * notinx(i)
	return ans
(n, k) = map(int, input().split())
print(int(solve(n, k)))


def C(n, k):
	result = 1
	for i in range(n - k + 1, n + 1):
		result *= i
	for i in range(2, k + 1):
		result //= i
	return result
(n, k) = map(int, input().split())
derangements = {2: 1, 3: 2, 4: 9}
result = 1
for (a, n_derang) in derangements.items():
	if a <= k:
		result += C(n, a) * n_derang
print(result)


import math

def ncr(n, r):
	f = math.factorial
	return f(n) // f(r) // f(n - r)
(n, k) = map(int, input().split())
if n == k:
	print(24)
elif k == 1:
	print(1)
elif k == 2:
	print(1 + ncr(n, 2))
elif k == 3:
	print(1 + ncr(n, 2) + ncr(n, 3) * 2)
elif k == 4:
	print(1 + ncr(n, 2) + ncr(n, 3) * 2 + ncr(n, 4) * 9)


(n, k) = map(int, input().split())
a = [0, 0, 1, 2, 9]
s = 0
for i in range(1, k + 1):
	x = 1
	y = 1
	p = n
	for j in range(1, i + 1):
		x = x * j
		y = y * p
		p -= 1
	s += y // x * a[i]
print(s + 1)


(n, k) = map(int, input().split())
answer = 0
if k > 1:
	answer += n * (n - 1) // 2
if k > 2:
	answer += n * (n - 1) * (n - 2) // 3
if k > 3:
	answer += n * (n - 1) * (n - 2) * (n - 3) // 8 * 3
print(int(answer + 1))


import sys
(n, k) = (int(i) for i in input().split())
ff = [1] * (n + 1)
for i in range(1, n + 1):
	ff[i] = ff[i - 1] * i
dd = [0] * (n + 1)
dd[1] = 0
dd[2] = 1
for i in range(3, n + 1):
	dd[i] = (i - 1) * (dd[i - 1] + dd[i - 2])
ans = ff[n]
for i in range(n - k):
	c = ff[n] // ff[n - i]
	c = c // ff[i]
	c = c * dd[n - i]
	ans -= c
print(ans)


(n, k) = map(int, input().split())
c = lambda i: c(i - 1) * (n - i + 1) // i if i else 1
print(sum([1, c(2), 2 * c(3), 9 * c(4)][:k]))


(n, k) = map(int, input().split())
ar = []
ar.append(1)
for i in range(1, n + 1):
	ar.append(ar[i - 1] * i)
k = n - k
ans = 0
br = []
br.append(1)
br.append(0)
for i in range(2, n + 1):
	br.append((i - 1) * (br[i - 1] + br[i - 2]))
for i in range(k, n + 1):
	ans = ans + ar[n] // (ar[i] * ar[n - i]) * br[n - i]
print(ans)


c = 1
(n, k) = map(int, input().split())
if k >= 2:
	tmp = 1
	for i in range(3, n + 1):
		tmp *= i
	for i in range(2, n - 1):
		tmp = tmp // i
	c += tmp
if k >= 3:
	tmp = 1
	for i in range(4, n + 1):
		tmp *= i
	for i in range(2, n - 2):
		tmp = tmp // i
	c += tmp * 2
if k == 4:
	tmp = 1
	for i in range(5, n + 1):
		tmp *= i
	for i in range(2, n - 3):
		tmp = tmp // i
	c += tmp * 9
print(c)


(n, k) = [int(x) for x in input().split(' ')]
ans = 1
if k >= 2:
	ans += n * (n - 1) // 2
if k >= 3:
	ans += n * (n - 1) * (n - 2) // 3
if k >= 4:
	ans += 9 * (n * (n - 1) * (n - 2) * (n - 3)) // 24
print(ans)


(n, k) = map(int, input().split())
ans = 1
ct = n
spoils = [0, 1, 1, 2, 9]
for i in range(2, k + 1):
	ct = ct * (n - i + 1) // i
	ans += ct * spoils[i]
print(ans)


import math
(n, k) = map(int, input().split(' '))

def combination(n, r):
	npr = math.factorial(n) // math.factorial(r)
	ncr = npr / math.factorial(n - r)
	return int(ncr)
dp = [1, 0, 1, 2, 9]
tem = 0
for _ in range(k + 1):
	tem += dp[_] * combination(n, _)
print(tem)


(n, k) = map(int, input().split())
answer = 1
if k > 1:
	answer += n * (n - 1) / 2
if k > 2:
	answer += n * (n - 1) * (n - 2) / 3
if k > 3:
	answer += n * (n - 1) * (n - 2) * (n - 3) / 24 * 9
print(int(answer))


dp = []
der = [0, 0, 1, 2, 9]

def comb(n, r):
	global dp
	if n == r or r == 0:
		return 1
	if dp[n][r] != 0:
		return dp[n][r]
	dp[n][r] = comb(n - 1, r) + comb(n - 1, r - 1)
	dp[n][n - r] = dp[n][r]
	return dp[n][r]
(n, k) = map(int, input().split())
if k == 1:
	print(1)
	exit(0)
dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
ans = 0
for i in range(n - k, n - 1):
	ans = ans + comb(n, i) * der[n - i]
print(ans + 1)


from sys import stdin, stdout

def solve(n):
	ret = factor[n]
	for i in range(1, n + 1):
		ret += (-1 if i % 2 == 1 else 1) * C[n][i] * factor[n - i]
	return ret
(n, k) = map(int, input().split())
C = [[0 for j in range(n + 1)] for i in range(n + 1)]
for i in range(n + 1):
	C[i][0] = C[i][i] = 1
	for j in range(1, i):
		C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
factor = [0] * 10
factor[0] = 1
for i in range(1, 10):
	factor[i] = factor[i - 1] * i
cnt = [0] * 5
cnt[0] = 1
for d in range(2, 5):
	cnt[d] = C[n][d] * solve(d)
ans = 0
for d in range(k + 1):
	ans += cnt[d]
print(ans)


from math import factorial as fact

def C(n, k):
	return fact(n) // (fact(k) * fact(n - k))
(n, k) = map(int, input().split())
sum = 0
for i in range(k + 1):
	if i == 0:
		sum += C(n, i)
	if i == 2:
		sum += C(n, i) * 1
	if i == 3:
		sum += C(n, i) * 2
	if i == 4:
		sum += C(n, i) * 9
print(sum)


from math import factorial

def fac(n, m):
	return factorial(n) // factorial(m) // factorial(n - m)
(n, k) = map(int, input().split())
if k == 1:
	print(1)
elif k == 2:
	print(fac(n, 2) + 1)
elif k == 3:
	print(fac(n, 3) * 2 + fac(n, 2) + 1)
elif k == 4:
	print(fac(n, 4) * 9 + fac(n, 3) * 2 + fac(n, 2) + 1)


import sys
input = sys.stdin.readline
from math import *
(n, k) = map(int, input().split())

def cof(n, k):
	C = [[0 for x in range(k + 1)] for x in range(n + 1)]
	for i in range(n + 1):
		for j in range(min(i, k) + 1):
			if j == 0 or j == i:
				C[i][j] = 1
			else:
				C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
	return C[n][k]

def deran(n, der):
	der[0] = 1
	der[1] = 0
	der[2] = 1
	for i in range(3, n + 1):
		der[i] = (i - 1) * (der[i - 1] + der[i - 2])
	return der[n]
c = 0
der = [0 for i in range(n + 10)]
deran(n, der)
for i in range(k + 1):
	p = cof(n, n - i)
	c += p * der[i]
print(c)


import sys

def main():
	args = sys.stdin.readline()[:-1].split()
	(n, k) = (int(args[0]), int(args[1]))
	a = 1
	b = n * (n - 1) // 2
	c = n * (n - 1) * (n - 2) // 6 * 2
	d = n * (n - 1) * (n - 2) * (n - 3) // 24 * 9
	if k == 1:
		print(a)
	if k == 2:
		print(a + b)
	if k == 3:
		print(a + b + c)
	if k == 4:
		print(a + b + c + d)
main()


d = [0, 0, 1, 2, 9]

def C(n, k):
	res = 1
	for i in range(1, k + 1):
		res = res * (n + 1 - i) // i
	return res
(n, k) = map(int, input().split())
res = 1
for i in range(k + 1):
	res += C(n, i) * d[i]
print(res)


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, k) = map(int, input().split())
comb = n
d = 1
s = 0
fact = 1
ans = 0
for i in range(k):
	ans += comb * (fact * s)
	comb *= n - i - 1
	comb = comb // (d + 1)
	d += 1
	s += (-1) ** i * Fraction(1, fact * (i + 2))
	fact *= i + 2
print(ans + 1)


n = [int(i) for i in input().split()]
r = [0 for i in range(4)]
r[0] = 1
r[1] = n[0] * (n[0] - 1) // 2
r[2] = n[0] * (n[0] - 1) * (n[0] - 2) // 3
r[3] = 9 * n[0] * (n[0] - 1) * (n[0] - 2) * (n[0] - 3) // (4 * 3 * 2)
sum1 = 0
for i in range(n[1]):
	sum1 += r[i]
print(sum1)


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

def f(n):
	if n == 1:
		return 0
	if n == 2:
		return 1
	return (n - 1) * (f(n - 1) + f(n - 2))

def g(n, k):
	res = 1
	for i in range(1, k + 1):
		res *= n - i + 1
		res //= i
	return res
res = 1
for i in range(1, k + 1):
	res += g(n, i) * f(i)
print(res)


(a, b) = map(int, input().split())
s = 1
if b >= 2:
	s += a * (a - 1) >> 1
if b >= 3:
	s += a * (a - 1) * (a - 2) / 3
if b == 4:
	s += 3 * a * (a - 1) * (a - 2) * (a - 3) >> 3
print(int(s))


from math import factorial as fac
pc = {3: 2, 2: 1, 4: 9}
(n, k) = [int(x) for x in input().split()]
good = 0
if k >= 2:
	cp = int(fac(n) / (fac(2) * fac(n - 2)))
	good += cp * pc[2]
if k >= 3:
	cp = int(fac(n) / (fac(3) * fac(n - 3)))
	good += cp * pc[3]
if k == 4:
	cp = int(fac(n) / (fac(4) * fac(n - 4)))
	good += cp * pc[4]
print(good + 1)


import operator as op
from functools import reduce
from itertools import permutations

def C(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
(n, k) = map(int, input().split())
d = [1]
for i in range(1, k + 1):
	p = [j for j in range(i)]
	x = 0
	for q in permutations(p):
		valid = True
		for j in range(len(q)):
			if j == q[j]:
				valid = False
		if valid:
			x += 1
	d.append(x)
answer = 0
for i in range(k + 1):
	answer += C(n, i) * d[i]
print(answer)


import sys

def gint():
	return int(input())

def read():
	return map(int, input().split())
(n, k) = read()
res = 1
if k >= 2:
	res += n * (n - 1) // 2
if k >= 3:
	res += n * (n - 1) * (n - 2) // 3
if k >= 4:
	res += n * (n - 1) * (n - 2) * (n - 3) * 3 // 8
print(res)


from math import factorial as f
(n, k) = map(int, input().split())
an = 0
dr = [0, 0, 1, 2, 9]
for i in range(n - k, n + 1):
	r = n - i
	if r == 0:
		an += 1
	elif r != 1:
		an += dr[r] * f(n) // (f(i) * f(n - i))
print(an)


import math
(n, k) = map(int, input().split())
der = [0 for i in range(1000 + 1)]
der[1] = 0
der[0] = 1
for i in range(2, n + 1):
	der[i] = (i - 1) * (der[i - 1] + der[i - 2])
ans = 0
for t in range(n - k, n + 1):
	bin = math.factorial(n) // (math.factorial(t) * math.factorial(n - t))
	ans += bin * der[n - t]
print(ans)


import math

def der(n):
	sm = 0
	p = 1
	for i in range(0, n + 1):
		sm += p * (math.factorial(n) // math.factorial(i))
		p = p * -1
	return sm

def nCr(n, r):
	f = math.factorial
	return f(n) // (f(r) * f(n - r))
(n, k) = (int(i) for i in input().split())
ans = 0
for i in range(0, k + 1):
	ans += nCr(n, i) * der(i)
print(ans)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
from collections import defaultdict
from itertools import permutations
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, k) = map(int, input().split())
r = 1
for i in range(2, k + 1):
	f = math.factorial(i)
	d = 0
	temp = 2
	ch = 1
	for j in range(2, n + 1):
		d += ch * (f // temp)
		temp *= j + 1
		ch = -1 * ch
	d2 = 1
	for j in range(2, i + 1):
		d2 *= j
	d1 = 1
	for j in range(n - i + 1, n + 1):
		d1 *= j
	r += d1 * d // d2
print(r)


mod = 1000000000.0 + 7

def power(a):
	re = 1
	for i in range(1, a + 1):
		re *= i
	return re

def func(n):
	if n == 0:
		return 1
	sum = 0
	for i in range(2, n + 1):
		sum += pow(-1, i) / power(i)
	return power(n) * sum

def C(a, b):
	return power(b) / (power(b - a) * power(a))
_in = input()
n = int(_in[:-1])
k = int(_in[-1:])
sum = 0
for i in range(n - k, n + 1):
	sum += C(i, n) * func(n - i)
print('%d' % sum)


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')

def power_set(L):
	cardinality = len(L)
	n = 2 ** cardinality
	powerset = []
	for i in range(n):
		a = bin(i)[2:]
		subset = []
		for j in range(len(a)):
			if a[-j - 1] == '1':
				subset.append(L[j])
		powerset.append(subset)
	powerset_orderred = []
	for k in range(cardinality + 1):
		for w in powerset:
			if len(w) == k:
				powerset_orderred.append(w)
	return powerset_orderred

def fastPlrintNextLines(a):
	print('\n'.join(map(str, a)))

def sortByFirstAndSecond(A):
	A = sorted(A, key=lambda x: x[0])
	A = sorted(A, key=lambda x: x[1])
	return list(A)
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = 1

def countDer(n):
	der = [0 for i in range(n + 1)]
	der[1] = 0
	der[2] = 1
	for i in range(3, n + 1):
		der[i] = (i - 1) * (der[i - 1] + der[i - 2])
	return der
for _ in range(t):
	(n, k) = li()
	ans = 1
	der = countDer(5)
	for i in range(k, 1, -1):
		ans += math.comb(n, i) * der[i]
	print(ans)


def bexpans(n, p):
	if p == 0:
		return 1
	else:
		return n * bexpans(n - 1, p - 1) // p
s = [1, 0, 1, 2, 9]
(n, k) = map(int, input().split())
res = sum((bexpans(n, i) * s[i] for i in range(k + 1)))
print(res)


def factorial(k):
	ans = 1
	for i in range(1, k + 1):
		ans *= i
	return ans
(n, k) = list(map(int, input().split()))
ans = 0

def A(n, m):
	ans = 1
	for x in range(m + 1, n + 1):
		ans *= x
	return ans
for i in range(2, k + 1):
	si = 0
	for j in range(2, i + 1):
		coeff = -1 if j % 2 else 1
		si += coeff / factorial(j)
	ans += A(n, n - i) * si
print(int(ans + 1.5))


import os
import sys
from io import BytesIO, IOBase

def main():
	(n, k) = map(int, input().split())
	su = 1
	if k >= 2:
		su += n * (n - 1) // 2
	if k >= 3:
		su += n * (n - 1) * (n - 2) // 3
	if k >= 4:
		su += 3 * n * (n - 1) * (n - 2) * (n - 3) // 8
	print(su)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(a, b) = map(int, input().split())
ans = 1
p = 1
aq = [1, 0, 1, 2, 9]
for i in range(1, b + 1):
	for j in range(min(a - i, i)):
		p *= (a - j) / (j + 1)
	ans += p * aq[i]
	p = 1
print(int(ans))


from math import factorial as f
from itertools import permutations
(n, k) = map(int, input().split())

def nCk(k):
	return f(n) // (f(k) * f(n - k))

def isBad(a):
	for (i, val) in enumerate(a):
		if i == val:
			return False
	return True
ret = 0
for cnt in range(k + 1):
	ways = nCk(cnt)
	badCnt = 0
	for p in permutations(range(cnt)):
		badCnt += isBad(p)
	ret += ways * badCnt
print(ret)


import sys
input = sys.stdin.readline

def fast_factorial(mod=None):
	res = [1, 1]
	size = 2

	def ff(k):
		nonlocal size
		while k >= size:
			res.append(res[-1] * size)
			size += 1
		return res[k]

	def ff_mod(k):
		nonlocal size
		while k >= size:
			res.append(res[-1] * (size % mod) % mod)
			size += 1
		return res[k]
	if mod == None:
		return ff
	else:
		return ff_mod
ff = fast_factorial()

def nCk(n, k):
	return ff(n) // (ff(k) * ff(n - k))
(n, k) = map(int, input().split())

def remain(n):
	nums = [-1] * n
	res = 0

	def solve(i):
		nonlocal nums, res
		if i == n:
			res += 1
			return
		for j in range(n):
			if i != j and (not j in nums):
				nums[i] = j
				solve(i + 1)
				nums[i] = -1
	solve(0)
	return res
res = 1
for c in range(n - k, n - 1):
	num = nCk(n, c) * remain(n - c)
	res += num
print(res)


import sys
ls = sys.stdin.readline().split(' ')
n = int(ls[0])
k = int(ls[1])
if k == 1:
	print(str(1))
elif k == 2:
	print(str(int(1 + n * (n - 1) / 2)))
elif k == 3:
	print(str(int(1 + n * (n - 1) / 2 + n * (n - 1) * (n - 2) / 3)))
elif k == 4:
	print(str(int(1 + n * (n - 1) / 2 + n * (n - 1) * (n - 2) / 3 + 3 * n * (n - 1) * (n - 2) * (n - 3) / 8)))


(n, k) = map(int, input().split())
facts = [1]
for i in range(1, n + 1):
	facts.append(i * facts[i - 1])
ans = facts[n]
if k >= 1:
	ans = 1
if k >= 2:
	ans += facts[n] // facts[n - 2] // facts[2]
if k >= 3:
	ans += 2 * facts[n] // facts[n - 3] // facts[3]
if k == 4:
	ans += 9 * facts[n] // facts[n - 4] // facts[4]
print(ans)


from sys import stdin, stdout
import math
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))

def ncr(n, r):
	lim = min(r, n - r)
	(num, den) = (n, 1)
	nn = dd = 1
	for i in range(lim):
		nn *= num
		dd *= den
		num -= 1
		den += 1
	return nn // dd
for _ in range(1):
	(n, k) = lst()
	dp = [0] * (1 + n)
	dp[1] = 0
	dp[2] = 1
	for i in range(3, n + 1):
		dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])
	sm = p = 0
	while p <= k:
		sm += ncr(n, p) * dp[p]
		p += 1
	print(sm + 1)


(n, k) = map(int, input().split())
if k == 1:
	print(1)
elif k == 2:
	print(1 + n * (n - 1) // 2)
elif k == 3:
	print(1 + n * (n - 1) * (n - 2) // 3 + n * (n - 1) // 2)
else:
	print(1 + n * (n - 1) // 2 + n * (n - 1) * (n - 2) // 3 + 3 * n * (n - 1) * (n - 2) * (n - 3) // 8)


def C(n, k):
	res = 1
	for i in range(1, k + 1):
		res *= n - i + 1
	for i in range(2, k + 1):
		res //= i
	return res
(n, k) = map(int, input().split())
ans = 1
val = {1: 1, 2: 2, 3: 9}
for i in range(k, 1, -1):
	ans += val[i - 1] * C(n, i)
print(ans)


import math

def comb(x, y):
	return math.factorial(x) // (math.factorial(x - y) * math.factorial(y))
s = input().split()
n = int(s[0])
k = int(s[1])

def Count_ALP_C(n, k):
	count = 0
	for m in range(k + 1):
		count += comb(n, m) * d(m)
	return count

def d(m):
	if m == 0:
		return 1
	if m == 1:
		return 0
	if m == 2:
		return 1
	if m == 3:
		return 2
	if m == 4:
		return 9
print(Count_ALP_C(n, k))


from math import *
from functools import *

def c(a, b):
	if b == 0:
		return 1
	y = 1
	for i in range(b + 1, a + 1):
		y *= i
	for i in range(1, a - b + 1):
		y /= i
	return y
(n, k) = map(int, input().split())
ans = 0
dr = [1, 0, 1]
for i in range(3, 1000):
	dr.append((i - 1) * (dr[i - 1] + dr[i - 2]))
for i in range(n - k, n + 1):
	choose = c(n, i)
	ans += dr[n - i] * choose
print(int(ans))


from itertools import permutations as perm
from math import factorial as fac

def calc(n):
	a = [i + 1 for i in range(n)]
	cnt = 0
	for i in perm(a):
		ok = True
		for (idx, j) in enumerate(i):
			if idx + 1 == j:
				ok = False
		cnt += 1 if ok else 0
	return cnt

def main():
	c = [calc(i + 1) for i in range(4)]
	(n, k) = map(int, input().split())
	fa = 1
	ans = 0
	for i in range(k):
		fa = fa * (n - i)
	while k > 0:
		if k == 1:
			ans = ans + 1
		else:
			ans = ans + fa // fac(k) * c[k - 1]
		k -= 1
		fa //= n - k
	print(ans)
	return
main()


(n, k) = [int(x) for x in input().split()]
if k == 1:
	print(1)
elif k == 2:
	print(int(n * (n - 1) / 2 + 1))
elif k == 3:
	print(int(n * (n - 1) * (n - 2) / 3 + n * (n - 1) / 2 + 1))
elif k == 4:
	print(int(3 * n * (n - 1) * (n - 2) * (n - 3) / 8 + n * (n - 1) * (n - 2) / 3 + n * (n - 1) / 2 + 1))


from sys import stdin, stdout
import math

def c(n, r):
	return math.factorial(n) // math.factorial(n - r) // math.factorial(r)
I = stdin.readline
P = stdout.write
(n, k) = map(int, I().split())
ans = 1
if k >= 2:
	ans += c(n, 2)
if k >= 3:
	ans += 2 * c(n, 3)
if k == 4:
	ans += 9 * c(n, 4)
P(str(ans))


def C(n, m):
	ans = 1
	for i in range(m):
		ans *= n - i
	for i in range(m):
		ans //= i + 1
	return ans
(n, m) = map(int, input().split())
ans = 1
if m >= 2:
	ans += C(n, 2)
if m >= 3:
	ans += C(n, 3) * 2
if m >= 4:
	ans += C(n, 2) * C(n - 2, 2) // 2
	ans += C(n, 4) * 6
print(ans)


(n, k) = map(int, input().split())
ans = 1
if k >= 2:
	ans += (n - 1) * n // 2
if k >= 3:
	ans += (n - 2) * (n - 1) * n // 6 * 2
if k >= 4:
	ans += (n - 3) * (n - 2) * (n - 1) * n // 24 * 9
print(ans)


inf = lambda : map(int, input().split())
(n, k) = inf()
ans = 1
c = n * (n - 1) // 2
if k >= 2:
	ans += c
	c = c * (n - 2) // 3
	if k >= 3:
		ans += c * 2
		c = c * (n - 3) // 4
		if k >= 4:
			ans += c * 9
print(ans)


S0 = [1, 0, 1, 2, 9]

def binom(n, p):
	return 1 if p == 0 else n * binom(n - 1, p - 1) // p
(n, k) = map(int, input().split())
res = sum((binom(n, i) * S0[i] for i in range(k + 1)))
print(res)


import operator as op
from functools import reduce

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer / denom

def countDer(n):
	der = [0 for i in range(n + 10)]
	der[0] = 1
	der[1] = 0
	der[2] = 1
	for i in range(3, n + 1):
		der[i] = (i - 1) * (der[i - 1] + der[i - 2])
	return der[n]
(n, k) = map(int, input().split())
ans = 0
for i in range(n - k, n + 1):
	ans += ncr(n, i) * countDer(n - i)
print(int(ans))


fact = [1]

def c_n_k(k, n):
	return fact[n] // (fact[k] * fact[n - k])
(n, k) = map(int, input().split())
for i in range(1, n + 1):
	fact.append(i * fact[i - 1])
ans = 1
d = [0, 0, 1, 3, 12, 60, 124]
for i in range(k, 1, -1):
	ans += c_n_k(i, n) * (d[i] - d[i] // i)
print(ans)


(n, k) = list(map(int, input().split()))
print(1 if k == 1 else n * (n - 1) // 2 + 1 if k == 2 else n * (n - 1) * (n - 2) // 3 + n * (n - 1) // 2 + 1 if k == 3 else n * (n - 1) * (n - 2) * (n - 3) * 9 // 24 + n * (n - 1) * (n - 2) // 3 + n * (n - 1) // 2 + 1)


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

def derangement(n):
	if n == 0 or n == 2:
		return 1
	if n == 1:
		return 0
	return (n - 1) * (derangement(n - 1) + derangement(n - 2))
f = [derangement(i) for i in range(k + 1)]

def C(n, m):
	z = 1
	for i in range(m):
		z = z * (n - i) // (i + 1)
	return z
ans = 0
for i in range(k + 1):
	ans += C(n, i) * f[i]
print(ans)


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

def bikkuri(n):
	ans = 1
	for i in range(1, n + 1):
		ans *= i
	return ans

def combination(n, r):
	return int(bikkuri(n) / (bikkuri(r) * bikkuri(n - r)))
q = [0, 0, 1]
for i in range(3, k + 1):
	q__ = q[i - 2]
	q_ = q[i - 1]
	qq = (i - 1) * (q__ + q_)
	q.append(qq)
ans = 1
for i in range(1, k + 1):
	ans += combination(n, i) * q[i]
print(ans)


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().strip().split(' '))

def msi():
	return map(str, input().strip().split(' '))

def li():
	return list(mi())

def dmain():
	sys.setrecursionlimit(1000000)
	threading.stack_size(1024000)
	thread = threading.Thread(target=main)
	thread.start()
import sys
input = sys.stdin.readline
scanner = lambda : int(input())
string = lambda : input().rstrip()
get_list = lambda : list(read())
read = lambda : map(int, input().split())
get_float = lambda : map(float, input().split())

def ceil(x):
	if x != int(x):
		x = int(x) + 1
	return x

def factorial(x, m):
	val = 1
	while x > 0:
		val = val * x % m
		x -= 1
	return val

def fact(x):
	val = 1
	while x > 0:
		val *= x
		x -= 1
	return val

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // math.gcd(a, b)

def is_integer(n):
	return math.ceil(n) == math.floor(n)

def nCr(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	if y == 0:
		return 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	(prime[0], prime[1]) = (False, False)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if n > 1:
		result = result * (1.0 - 1.0 / float(n))
	return int(result)

def is_prime(n):
	if n == 0:
		return False
	if n == 1:
		return True
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def next_prime(n, primes):
	while primes[n] != True:
		n += 1
	return n
MAXN = int(100000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
spf = [0 for i in range(MAXN)]

def factoriazation(x):
	res = []
	for i in range(2, int(x ** 0.5) + 1):
		while x % i == 0:
			res.append(i)
			x //= i
	if x != 1:
		res.append(x)
	return res

def factors(n):
	res = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			res.append(i)
			res.append(n // i)
	return list(set(res))

def int_array():
	return list(map(int, input().strip().split()))

def float_array():
	return list(map(float, input().strip().split()))

def str_array():
	return input().strip().split()

def binary_search(low, high, w, h, n):
	while low < high:
		mid = low + (high - low) // 2
		if check(mid, w, h, n):
			low = mid + 1
		else:
			high = mid
	return low

def check(moves, n):
	val = (moves + 1) // 2
	rem = moves - val
	sol = (val + 1) * (rem + 1)
	return sol < n

def sortSecond(val):
	return val[1]
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
alphs = 'abcdefghijklmnopqrstuvwxyz'
from itertools import permutations
import math
import bisect as bis
import random
import sys
import collections as collect
import functools as fnt
from decimal import Decimal

def solve():
	(n, k) = read()
	derangements = [1, 0, 1, 2, 9]
	ans = 1
	for i in range(1, k + 1):
		ans += nCr(n, i) * derangements[i]
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = 1
for i in range(t):
	solve()


import math
R = lambda : map(int, input().split())
(n, k) = R()
cnt = [1, 0, 1, 2, 9]
res = 0
for i in range(k + 1):
	res += math.factorial(n) // (math.factorial(i) * math.factorial(n - i)) * cnt[i]
print(res)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def fact(n):
	if n == 0:
		return 1
	p = 1
	for i in range(1, n + 1):
		p = p * i
	return p

def de(n):
	o = 0
	a = fact(n)
	for i in range(n + 1):
		o = o + a * (-1) ** i / fact(i)
	return o
(n, k) = invr()
out = 0
for i in range(n - k, n + 1):
	out = out + fact(n) / (fact(i) * fact(n - i)) * de(n - i)
print(int(out))


(n, k) = map(int, input().split())
a = n * (n - 1) // 2
b = a * (n - 2) // 3
c = b * (n - 3) // 4
print(sum([1, 0, a, 2 * b, 9 * c][:k + 1]))


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r):
	num = den = 1
	for i in range(r):
		num = num * (n - i)
		den = den * (i + 1)
	return num // den

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def digits(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return map(int, input().split())

def fact(n):
	ans = 1
	for i in range(n):
		ans = ans * (i + 1)
	return ans

def de(k):
	if k == 0:
		return 0
	temp = fact(k)
	aa = 0
	for i in range(k - 1):
		if i & 1:
			aa -= temp // fact(i + 2)
		else:
			aa += temp // fact(i + 2)
	return aa
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, k) = map(int, input().split())
ans = 0
for i in range(k):
	a = ncr(n, k - i)
	b = de(k - i)
	ans += a * b
print(ans + 1)


(n, k) = list(map(int, input().split()))
(p, q, r) = (n * (n - 1) // 2, n * (n - 1) * (n - 2) // 6, n * (n - 1) * (n - 2) * (n - 3) // 24)
if k < 2:
	print(1)
elif k == 2:
	print(1 + p)
elif k == 3:
	print(1 + p + 2 * q)
elif k == 4:
	print(1 + p + 2 * q + 9 * r)


def main():
	(n, k) = (int(y) for y in input().split())
	solver(n, k)

def solver(n, k):
	nck = [None] * (n + 1)
	nck[0] = 1
	for i in range(1, n + 1):
		nck[i] = nck[i - 1] * (n - i + 1) // i
	der = [None] * (n + 1)
	der[0] = 1
	der[1] = 0
	der[2] = 1
	for i in range(3, n + 1):
		der[i] = (i - 1) * (der[i - 1] + der[i - 2])
	result = sum([nck[i] * der[i] for i in range(k + 1)])
	print(result)
main()


import sys
sys.setrecursionlimit(1500)

def fact(n):
	f = {}
	if n in f:
		return f[n]
	elif n == 0 or n == 1:
		return 1
	else:
		return n * fact(n - 1)
import math
D = [0, 0, 1, 2, 9]

def ans(n, k):
	N = fact(n)
	Ans2 = 0
	for i in range(k, 1, -1):
		r = fact(i)
		n_minus_r = fact(n - i)
		temp2 = N // (n_minus_r * r)
		Ans2 += temp2 * D[i]
	return 1 + Ans2
(n, k) = map(int, input().split())
if k == 1:
	print(1)
else:
	print(ans(n, k))


import math
(n, k) = map(int, input().split())
fact = [1] * (n + 1)
for i in range(2, n + 1):
	fact[i] = fact[i - 1] * i

def Rec2(n):
	res = 0
	for i in range(0, n + 1):
		fa = math.pow(-1, i)
		if i == 0:
			fa = 1
		res += fact[n] * fa / fact[i]
	return abs(res)

def Rec(n, k):
	if k == 1:
		return 1
	result = 0
	result += fact[n] / (fact[k] * fact[n - k]) * Rec2(k)
	return result
res = 0
for i in range(1, k + 1):
	res += Rec(n, i)
print(int(res))


from math import factorial

def comb(n, r):
	if r == 1:
		return n
	elif r == 2:
		return n * (n - 1) // 2
	elif r == 3:
		return n * (n - 1) * (n - 2) // 6
	else:
		return n * (n - 1) * (n - 2) * (n - 3) // 24

def derange(n):
	if n == 1:
		return 0
	elif n == 2:
		return 1
	elif n == 3:
		return 2
	elif n == 4:
		return 9
(n, k) = map(int, input().split())
ans = 0
for i in range(1, k + 1):
	ans += comb(n, i) * int(derange(i))
print(ans + 1)


def fall_fac(n, k):
	ans = 1
	for i in range(k):
		ans *= n - i
	return ans

def C(n, k):
	if not 0 <= k <= n:
		return 0
	else:
		return fall_fac(n, k) // fall_fac(k, k)

def derangement(n):
	if n == 0:
		return 1
	elif n == 1:
		return 0
	else:
		return (n - 1) * (derangement(n - 1) + derangement(n - 2))
(n, k) = [int(x) for x in input().split()]
print(sum([C(n, i) * derangement(i) for i in range(k + 1)]))


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, k) = list(map(int, input().split()))
arr = [1, 0, n * (n - 1) // 2]
arr.append(n * (n - 1) * (n - 2) // 3)
arr.append(n * (n - 1) * (n - 2) * (n - 3) * 3 // 8)
print(sum(arr[:k + 1]))


from math import factorial as fact
(n, k) = map(int, input().split())
ans = 1
while k != 1:
	if k == 4:
		ans += 9 * (fact(n) // (fact(k) * fact(n - k)))
	elif k == 3:
		ans += 2 * (fact(n) // (fact(k) * fact(n - k)))
	else:
		ans += fact(n) // (fact(k) * fact(n - k))
	k -= 1
print(ans)


def factorial(num):
	if num == 1:
		return 1
	return num * factorial(num - 1)

def nCr(n, r):
	f = factorial
	output = 1
	for i in range(r):
		output *= n - i
	return output / f(r)

def kOne(num):
	return 1

def kTwo(n):
	return int(n * (n - 1) / 2)

def kThree(n):
	return 2 * nCr(n, 3)

def kFour(n):
	return 9 * nCr(n, 4)
inp = input().split(' ')
n = int(inp[0])
k = int(inp[1])
total = 0
if k >= 1:
	total += kOne(n)
if k >= 2:
	total += kTwo(n)
if k >= 3:
	total += kThree(n)
if k >= 4:
	total += kFour(n)
print(int(total))


(n, k) = map(int, input().split())
ans = [1, 0]
ans.append(n * (n - 1) // 2)
ans.append(n * (n - 1) * (n - 2) // 3)
ans.append(n * (n - 1) * (n - 2) * (n - 3) * 3 // 8)
print(sum(ans[:k + 1]))


import math

def derange(n):
	return int(math.factorial(n) * sum([(-1) ** i / math.factorial(i) for i in range(n + 1)]))

def choose(n, k):
	ans = 1
	if n - k < k:
		k = n - k
	for i in range(k):
		ans *= n - i
	ans /= math.factorial(k)
	return int(ans)

def almostIdent(n, k):
	ans = 0
	for i in range(k + 1):
		ans += choose(n, n - i) * derange(i)
	return ans
s = input().split(' ')
n = int(s[0])
k = int(s[1])
print(almostIdent(n, k))


from itertools import combinations, permutations, combinations_with_replacement
(n, k) = [int(i) for i in input().split()]
keys = range(n)

def fac(n):
	f = 1
	for i in range(1, n + 1):
		f = f * i
	return f

def comb(n, k):
	return fac(n) / (fac(n - k) * fac(k))
c = 0
for i in range(1, k + 1):
	if i == 1:
		c += 1
	if i == 2:
		c += comb(n, n - i)
	if i == 3:
		c += comb(n, n - i) * 2
	if i == 4:
		c += comb(n, n - i) * 9
print(int(c))


(n, k) = map(int, input().split())
ans = 1
get = n
s = [0, 1, 1, 2, 9]
for i in range(2, k + 1):
	get = get * (n - i + 1) // i
	ans += get * s[i]
print(ans)


ls = list(map(int, input().split()))
n = ls[0]
k = ls[1]
s = 0
for i in range(1, k + 1):
	if i == 1:
		s += 1
	elif i == 2:
		s += n * (n - 1) // 2
	elif i == 3:
		s += 2 * n * (n - 1) * (n - 2) // 6
	elif i == 4:
		s += 9 * n * (n - 1) * (n - 2) * (n - 3) // 24
print(s)


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

def ncr(n, r):
	num = den = 1
	for i in range(r):
		num = num * (n - i)
		den = den * (i + 1)
	return num // den
deara = [0, 0, 1, 2, 9]
total = 0
for i in range(2, k + 1):
	total += ncr(n, n - i) * deara[i]
print(total + 1)


import os
import sys
import math
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	(n, k) = map(int, input().split())
	ret = 1
	cnt = [0, 1, 2, 9]
	dp = [[0 for i in range(k + 1)] for i in range(n + 1)]
	dp[0][0] = 1
	for i in range(1, n + 1):
		dp[i][0] = 1
	for i in range(1, n + 1):
		for j in range(1, k + 1):
			dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
	for i in range(2, k + 1):
		ret += dp[n][i] * cnt[i - 1]
	print(ret)
main()


import math
from sys import stdin
string = stdin.readline().strip().split()
n = int(string[0])
k = int(string[1])

def factorial(N):
	result = 1
	for i in range(1, N + 1):
		result *= i
	return result
output = 1
for i in range(2, k + 1):
	if i == 2:
		output = output + factorial(n) / factorial(n - 2) / 2
	if i == 3:
		output = output + 2 * (factorial(n) / factorial(n - 3) / 6)
	if i == 4:
		output = output + 9 * (factorial(n) / factorial(n - 4) / 24)
print(int(output))


(n, k) = map(int, input().split())
c = [1, 0, 1, 2, 9]
a = [1, n, 0, 0, 0]
a[2] = a[1] * (n - 1) // 2
a[3] = a[2] * (n - 2) // 3
a[4] = a[3] * (n - 3) // 4
ans = 1
if k >= 2:
	ans += a[2] * c[2]
if k >= 3:
	ans += a[3] * c[3]
if k >= 4:
	ans += a[4] * c[4]
print(ans)


def nCr(n, r):
	p = 1
	for i in range(n, n - r, -1):
		p *= i
	for i in range(1, r + 1):
		p //= i
	return p
(n, k) = list(map(int, input().split()))
out = 1
if k >= 2:
	out += nCr(n, 2)
if k >= 3:
	out += 2 * nCr(n, 3)
if k == 4:
	out += 9 * nCr(n, 4)
print(out)


from collections import defaultdict, OrderedDict, Counter
from sys import stdin, stdout
from bisect import bisect_left, bisect_right
from queue import Queue
from statistics import median
from math import gcd, sqrt, floor, factorial, ceil, log2, log10
import copy
from copy import deepcopy
import sys
sys.setrecursionlimit(10 ** 7)
import math
import os
import bisect
import collections
mod = pow(10, 9) + 7

def ncr(n, r, p=mod):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
inf = float('inf')
adj = defaultdict(set)
visited = defaultdict(int)

def addedge(a, b):
	adj[a].add(b)
	adj[b].add(a)

def bfs(v):
	q = Queue()
	q.put(v)
	visited[v] = 1
	while q.qsize() > 0:
		s = q.get_nowait()
		print(s)
		for i in adj[s]:
			if visited[i] == 0:
				q.put(i)
				visited[i] = 1

def dfs(v, visited):
	if visited[v] == 1:
		return
	visited[v] = 1
	print(v)
	for i in adj[v]:
		dfs(i, visited)

def fun(n, k):
	if k == 1:
		return 1
	if k == 2:
		return 1 + n * (n - 1) // 2
	if k == 3:
		return 2 * n * (n - 1) * (n - 2) // 6 + fun(n, 2)
	if k == 4:
		return 9 * n * (n - 1) * (n - 2) * (n - 3) // 24 + fun(n, 3)
(n, k) = map(int, input().split())
ans = fun(n, k)
print(ans)


(n, k) = map(int, input().strip().split())
d = [0, 0]
for i in range(k - 1):
	d.append(d[-1] * (i + 2) + (-1) ** (i + 2))
ans = 0
sel = 1
for i in range(k + 1):
	ans += sel * d[i]
	sel = int(sel * (n - i) / (i + 1))
print(ans + 1)


from math import factorial as fact

def ncr(n, k):
	ans = 1
	den = 1
	for i in range(1, k + 1):
		ans *= n - i + 1
		den *= i
	return ans // den
(n, k) = map(int, input().split())
ans = 1
der = [1, 0, 1, 2, 9]
for i in range(1, k + 1):
	ans += ncr(n, i) * der[i]
print(ans)


A = input().split()
n = int(A[0])
k = int(A[1])
fact = [1] * (n + 1)
for i in range(1, n + 1):
	fact[i] = fact[i - 1] * i
der = [1] * (n + 1)
der[0] = 1
der[1] = 0
for i in range(2, n + 1):
	der[i] = (i - 1) * (der[i - 1] + der[i - 2])

def comb(n, k):
	return fact[n] // (fact[k] * fact[n - k])
tot = 0
for i in range(0, k + 1):
	tot = tot + comb(n, i) * der[i]
print(tot)


(n, k) = map(int, input().split())
ans = 1
p = [0, 1, 1, 2, 9]
t = n
for i in range(2, k + 1):
	t = t * (n - i + 1) // i
	ans += t * p[i]
print(ans)


from math import factorial

def c(n, k):
	return factorial(n) / (factorial(n - k) * factorial(k))
ar = [1, 1, 2, 9]
(n, k) = map(int, input().split())
if k == 1:
	print(1)
else:
	ans = 1
	for i in range(2, k + 1):
		ans += c(n, i) * ar[i - 1]
	print(int(ans))


(n, k) = map(int, input().split(' '))
k = n - k
import math

def ncr(n, r):
	return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))
from itertools import permutations

def left_one(left):
	temp = [x for x in range(left)]
	cnt = 0
	allperm = list(permutations(temp))
	for x in allperm:
		chk = 0
		for z in range(len(x)):
			if x[z] == z:
				chk = 1
				break
		if chk == 0:
			cnt += 1
	return cnt
ans = 1
for x in range(k, n):
	ans += ncr(n, x) * left_one(n - x)
print(ans)


import math
nk = input().split()
n = int(nk[0])
k = int(nk[1])
L = [0] * 5
L[1] = 1
L[2] = n * (n - 1) // 2
L[3] = n * (n - 1) * (n - 2) // 3
L[4] = 3 * n * (n - 1) * (n - 2) * (n - 3) // 8
s = 0
for i in range(0, k + 1):
	s += L[i]
print(s)


(n, k) = map(int, input().split())
vet = [1]
vet.append(n * (n - 1) // 2 + vet[0])
vet.append(n * (n - 1) * (n - 2) // 3 + vet[1])
vet.append(3 * n * (n - 1) * (n - 2) * (n - 3) // 8 + vet[2])
print(vet[k - 1])


(n, k) = map(int, input().split())
ls = [1, 0, 0, 0, 0]
ls[2] = n * (n - 1) // 2
ls[3] = n * (n - 1) * (n - 2) // 3
ls[4] = n * (n - 1) * (n - 2) * (n - 3) * 3 // 8
print(sum(ls[:k + 1]))


(n, k) = input().split()
(n, k) = (int(n), int(k))
if k == 1:
	(print(1), exit())
s = 1

def f(x):
	d = 1
	for i in range(2, x + 1):
		d *= i
	return d

def g(x):
	d = 0
	for i in range(x + 1):
		d += f(x) // f(i) * (-1) ** i
	return d
for i in range(2, k + 1):
	d = 1
	d *= f(n) // f(n - i) // f(i)
	d *= g(i)
	s += d
print(s)


import sys
from math import factorial
from functools import reduce
from operator import mul
(n, k) = map(int, input().split())
montmort = [0, 0, 1, 2, 9]
ans = 1
for x in range(2, k + 1):
	ans += reduce(mul, range(n, n - x, -1), 1) // factorial(x) * montmort[x]
print(ans)


import itertools

def C(n, m):
	ret = 1
	for i in range(m):
		ret *= n - i
	for i in range(m):
		ret //= i + 1
	return ret
(n, k) = map(int, input().split())
d = [0] * (k + 1)
for m in range(k + 1):
	p = list()
	for i in range(m):
		p.append(i)
	pp = itertools.permutations(p)
	for permutation in pp:
		ok = True
		for i in range(m):
			if permutation[i] == i:
				ok = False
				break
		if ok:
			d[m] += 1
ans = 0
for m in range(k + 1):
	ans += C(n, m) * d[m]
print(ans)


n = [int(i) for i in input().split()]
if n[1] == 1:
	print('1')
elif n[1] == 2:
	print(int(n[0] * (n[0] - 1) / 2 + 1))
elif n[1] == 3:
	print(int(n[0] * (n[0] - 1) / 2 + 1 + n[0] * (n[0] - 1) * (n[0] - 2) / 3))
elif n[1] == 4:
	print(int(n[0] * (n[0] - 1) / 2 + 1 + n[0] * (n[0] - 1) * (n[0] - 2) / 3 + 3 / 8 * n[0] * (n[0] - 1) * (n[0] - 2) * (n[0] - 3)))


def intersect_size(n, m):
	val = 1
	exponent = n - m
	term = n
	while exponent > 0:
		val *= term
		term -= 1
		exponent -= 1
	return val
mem_comb = {}

def comb(n, k):
	if n < 0 or k < 0 or n < k:
		return 0
	elif k == 0 or k == n:
		return 1
	elif (n, k) not in mem_comb:
		m = 1
		val = 1
		while m <= k:
			val *= n + 1 - m
			val /= m
			m += 1
		val = round(val)
		mem_comb[n, k] = val
	return mem_comb[n, k]

def at_least_occurrences(n, k):
	return sum(((-1) ** j * comb(n - k + j - 1, j) * intersect_size(n, n - k + j) for j in range(k + 1)))
(n, k) = [int(x) for x in input().split(' ')]
if n == k:
	print(intersect_size(n, 0))
else:
	print(at_least_occurrences(n, k))


(n, k) = list(map(int, input().split()))
if k == 1:
	print(1)
elif k == 2:
	print(n * (n - 1) // 2 + 1)
elif k == 3:
	print(n * (n - 1) * (n - 2) // 3 + n * (n - 1) // 2 + 1)
elif k == 4:
	print(n * (n - 1) * (n - 2) * (n - 3) * 9 // 24 + n * (n - 1) * (n - 2) // 3 + n * (n - 1) // 2 + 1)


import sys
import math

def derange(k):
	ans = math.factorial(k)
	z = -1
	mult = 1
	for i in range(1, k + 1):
		mult += z * (1 / math.factorial(i))
		z *= -1
	ans = ans * mult
	return int(ans)

def com(n, k):
	if k == 0:
		return 1
	if k == 1:
		return n
	if k == 2:
		return n * (n - 1) // 2
	if k == 3:
		return n * (n - 1) * (n - 2) // 6
	return n * (n - 1) * (n - 2) * (n - 3) // 24
(n, k) = map(int, sys.stdin.readline().split())
ans = 0
for i in range(k + 1):
	x = com(n, i) * derange(i)
	ans += x
print(ans)


from math import factorial as fac

def binomial(x, y):
	try:
		binom = fac(x) // fac(y) // fac(x - y)
	except ValueError:
		binom = 0
	return binom
(n, k) = [int(i) for i in input().split()]
if k == 1:
	print(1)
elif k == 2:
	print(binomial(n, 2) + 1)
elif k == 3:
	print(binomial(n, 3) * 2 + binomial(n, 2) + 1)
elif k == 4:
	print(binomial(n, 4) * 9 + binomial(n, 3) * 2 + binomial(n, 2) + 1)


(k, kk) = map(int, input().split())
c = 0
if kk >= 1:
	c = 1
if kk > 1:
	c += k * (k - 1) / 2
if kk > 2:
	c += k * (k - 1) * (k - 2) / 6 * 2
if kk > 3:
	c += k * (k - 1) * (k - 2) * (k - 3) / 24 * 9
print(int(c))