有多少个字符集大小为 $|\Sigma |$ 、长度为 $n$ 的字符串满足其不存在长度为 $k$ 的回文子串，答案对 $10^9 + 7$ 取模。

输入格式：一行三个正整数分别表示 $|\Sigma|$，$n$，$k$。

输出格式：输出一行一个数表示答案

Sample

保证 $1\le |\Sigma|\le 10^9 + 7$，$1\le n\le 1000$，$2\le k\le 25$。