题目描述

给定字符集大小 $\sigma$、字符串长度 $n$ 和整数 $k$，询问长度为 $n$ 且不存在长度为 $k$ 的回文子串的字符串个数，对 $10^9+7$ 取模。

输入格式

输入的第一行包含三个整数 $\sigma,n,k$，分别表示字符集大小、字符串长度、回文子串长度。

输出格式

输出一行一个整数，表示答案，对 $10^9+7$ 取模。

样例

输入

3 5 3

输出

72

数据范围

本题开启子任务评测。

对于所有数据，保证

$$1\le \sigma\le 10^9+7,\quad 1\le n\le 1000,\quad 2\le k\le 25.$$

子任务编号	$n\le$	$k\le$	子任务分值
1	10	25	10
2	1000	2
3		7	30
4	300	25
5	1000		20