888_D. Almost Identity Permutations
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
```python
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)



```