Logo CSP.ac

CSP.ac

1 s / 256 MB

#120. 【冬令营】Day1T3-字符串计数

统计

【问题描述】

有n种不同的字符,不妨用1到n来编号。如果一个字符串的长度不超过m,且长度至少为1,而且字符串中相邻字符不相同,

那么这个字符串是合法的。如果一个字符串中出现过的编号最小的字符的编号是k,那么这个字符串的权值是k。

求所有合法字符串的权值之和。

【输入格式】

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

【输出格式】

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

【样例输入1】

3 2

【样例输出1】

14

【样例解释1】

字符串分别是

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

【样例输入2】

15 1

【样例输出2】

120

【样例输入3】

123456789 233

【样例输出3】

119890141

【数据规模和约定】

对于20%的数据, n<=1000,m<=3

对于50%的数据, n<=10^9,m<=3

对于80%的数据, n<=10^9,m<=100

对于100%的数据,n<=10^9,m<=1000