有 $n$ 种不同的字符，我们用 $1$ 到 $n$ 来编号。如果一个字符串的长度不超过 $m$，且长度至少为 $1$，而且字符串中相邻字符不相同，那么字符串是合法的。
如果一个字符串中出现的编号最小字符的编号是 $k$，那么这个字符串的权值是 $k$。
求所有合法字符串的权值之和。

一行两个正整数，分别是 $n$ 和 $m$。

一行一个数，表示所有合法字符串的权值之和。
由于数会很大，对 $10^9+7$ 取模。

对于 $20\%$ 的数据，$n \leq 1000,\ m \leq 3$。
对于 $50\%$ 的数据，$n \leq 10^9,\ m \leq 3$。
对于 $50\%$ 的数据，$n \leq 10^9,\ m \leq 100$。
对于 $100\%$ 的数据，$n \leq 10^9,\ m\leq 1000$。

14

字符串分别是
1        权值为 $1$
2        权值为 $2$
3        权值为 $3$
12       权值为 $1$
13       权值为 $1$
21       权值为 $1$
23       权值为 $2$
31       权值为 $1$
32       权值为 $2$
总权值为：$1+2+3+1+1+1+2+1+2=14$