Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Almost Identity Permutations

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA 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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/20/2018 11:37:32 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|