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

Difficulty: interview

Starter code:

Solutions:
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)

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] * 3

dd[1] = 0
dd[2] = 1

for i in range(3, n + 1) :
	dd.append((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)

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)


# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

"""
created by shhuan at 2017/11/9 23:24

"""


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)


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

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

n, k = list(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]))





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


"""
while 1:
    n, k = map(int, input().split())
    
    def solve(n, k):
        from itertools import permutations
        res = 0
        for p in permutations([i for i in range(n)]):
            c = sum(i == p[i] for i in range(n))
            if c >= n - k: res += 1
        return res
    
    print(solve(n, k))
""" 
n, k = map(int, 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 += n * (n - 1) * (n - 2) * (n - 3) // 24 * 9
print(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)

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

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)

#D
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))

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


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)
    


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

#k = n - k
#k += 1
#n += 1
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, f(nr) // (f(i) * f(n - i)))
print(an)


from itertools import combinations, permutations, combinations_with_replacement

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

keys = list(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))



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


n,k=list(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)


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

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



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)