题目描述

求有多少长度为 $n$ 的数列 $A$，满足以下条件：

• $1\leq A_i \leq M$ $(1 \le i \le N)$
• $|A_i - A_{i+1}| \geq K$ $(1 \le i\le N-1)$

输入格式

第一行输入三个整数 $N$ $M$ $K$

输出格式

输出一个整数

2 3 1

6

3 3 2

2

100 1000 500

657064711

样例 1 解释

有这 $6$ 个分别是。 - $(1,2)$ - $(1,3)$ - $(2,1)$ - $(2,3)$ - $(3,1)$ - $(3,2)$

提示

• $2\ \leq\ N\ \leq\ 1000$
• $1\ \leq\ M\ \leq\ 5000$
• $0\ \leq\ K\ \leq\ M-1$