← 返回题目列表

Codeforces · 888/D

D. 几乎身份排列

中文机器翻译题面 查看原题

大小为 n 的排列 p 是一个数组,从 1 到 n 的每个整数在此数组中恰好出现一次。

让我们将排列称为几乎恒等排列,当且仅当存在至少 n - k 个索引 i (1 ≤ i ≤ n) 使得 pi = i。

你的任务是计算给定数字 n 和 k 的几乎恒等排列的数量。

输入

第一行包含两个整数 n 和 k (4 ≤ n ≤ 1000, 1 ≤ k ≤ 4)。

输出

打印给定 n 和 k 的几乎恒等排列的数量。

示例

输入 #1

4 1

输出 #1

1

输入 #2

4 2

输出 #2

7

输入 #3

5 3

输出 #3

31

输入#4

5 4

输出#4

76