bzoj#P3157. 国王奇遇记

国王奇遇记

题目描述

Katharon 国有着悠久的历史,每个慕名而来的游客都渴望能在 Katharon 国发现一些奇怪的宝藏。而作为国王的 Kanari 君也梦想着有一天发现自己国家的宝藏,从而成为世界上最富有的人。 Kanari 国王和 katherine 皇后凭着 14 年真挚的感情,数十年如一日甜蜜地生活在一起。前几天恰逢劳动节放假, Kanari 国王便和 Katherine 皇后一同前往电影院观看了最新出版的电影《致青春》。看完之后两人对青春又有了更深刻的认识。然而在返程的路上,他们突然在路边的小树林里发现了一块奇怪的石板,上面印着一行小字:“如果你能破解下面表达式的结果,你就可以拥有 Katharon 国最珍贵的财产。”这时 Kanari 国王和 Katherine 皇后再也顾不上秀恩爱了,只好拿出草纸拼命计算这个表达式的结果。可是两人能力有限,现在,他们找到擅长数学的你,想请你来帮助他们完成这个愿望,如果你能回答正确,他们愿意把 Katharon 国最珍贵的财产分给你一半哦。这个表达式就是:

i=1nim×mi\sum_{i=1}^n i^m \times m^i

输入格式

共一行,包括两个正整数 nnmm

输出格式

共一行,为所求表达式的值对 109+710^9+7 取模的值。

样例输入

5 3

样例输出

36363

数据规模与约定

1n109,1m2001\le n\le 10^9,1\le m \le 200

题目来源

Katharon+#1