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

=====
Give me a Python code to print the number of almost identity permutations for given n and k?
assistant
#Here is Python code to print the number of almost identity permutations for given n and 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)