human
Give me a Python code to print the number of almost identity permutations for given n and k given the following:
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 pi = 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
Solve the task in PYTHON3.
assistant
#Here is Python code to print the number of almost identity permutations for given n and k.

import sys
input = sys.stdin.readline

'''

'''

def fast_factorial(mod=None):
    """
    Faster than naive factorial, uses memoization.
    """
    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:
            #print(nums)
            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  

#remain(4)

res = 1
for c in range(n-k, n-1):
    num = nCk(n, c) * remain(n-c)
    res += num
print(res)