存在一个大小为 $k$ 的字母表。对于该字母表中的字符串 $S$（文本）和字符串 $P$（模式串），令 $F(S, P)$ 为在 $S$ 中能够选出的互不重叠且等于 $P$ 的子串的最大数量。

如果一个字符串 $Q$ 中每个字符出现的次数都不超过 2 次，则称其为“优美”的。

对于所有长度为 $n$ 的字符串 $S$ 以及所有长度为 $m$ 的优美模式串 $P$，计算 $F(S, P)$ 的总和。由于该总和可能非常大，请输出结果对 $10^9 + 7$ 取模后的值。

输入格式

输入仅一行，包含 3 个整数 $n, m, k$（$1 \le n \le 10^6$，$1 \le m \le 2000$，$m \le n$ 且 $1 \le k \le 10^9$），分别表示字符串 $S$ 的长度、模式串 $P$ 的长度以及字母表的大小。

输出格式

输出一行，包含一个整数，表示所有字符串 $S$ 和优美字符串 $P$ 的 $F(S, P)$ 之和，对 $10^9 + 7$ 取模。

样例

输入 1

4 2 3

输出 1

228

输入 2

999999 1999 12345678

输出 2

52352722