题目描述

在一条数轴上，从 0 至 N 共有 N+1 个整点，分别是： 0 , 1 , 2 , 3 , 4 ,..., N 。有 K 头奶牛，每头奶牛选择一个整点作为它们的家，但它们不能选择相同的整点。为了方便联络，住得最远的那两头奶牛的距离必须等于 D 。问有多少种不同的方案？

出题人觉得这题不错， 于是把这题给大家做， 但为了降低难度， 于是把上面的题目做了一个改变： K=3 ，即只有 3 头奶牛。

输入格式

一行，两个正整数， N 和 D。

数据范围

对于50%的数据， 1<=N<=100 , 2<=D<=N 。

对于100%的数据， 1<=N<=500000 , 2<=D<=N 。

输出格式

一个整数。

样例

2 2

6

5 3

36

500000 20000

57597239994

样例解释

样例 1 说明：

• 方案 1 ：奶牛 A 选择整点 0 ，奶牛 B 选择整点 1 ，奶牛 C 选择整点 2 。

• 方案 2 ：奶牛 A 选择整点 0 ，奶牛 C 选择整点 1 ，奶牛 B 选择整点 2 。

• 方案 3 ：奶牛 B 选择整点 0 ，奶牛 A 选择整点 1 ，奶牛 C 选择整点 2 。

• 方案 4 ：奶牛 B 选择整点 0 ，奶牛 C 选择整点 1 ，奶牛 A 选择整点 2 。

• 方案 5 ：奶牛 C 选择整点 0 ，奶牛 A 选择整点 1 ，奶牛 B 选择整点 2 。

• 方案 6 ：奶牛 C 选择整点 0 ，奶牛 B 选择整点 1 ，奶牛 A 选择整点 2 。

温馨提示

答案可能较大，建议读入的变量 N 、D 以及程序中你用到的其他变量，都定义为 long long 类型。