#P3157. 国王奇遇记

    ID: 2333 传统题 1000ms 512MiB 尝试: 1136 已通过: 481 难度: 6 上传者: 标签>难度分类提高构造与建模差分转化动态规划线性 DP组合数学Pascal 递推数论模逆元快速幂CF2100Katharon+#1

国王奇遇记

国王奇遇记

题目描述

游客们常来历史悠久的 Katharon 国寻找宝藏,Kanari 国王也希望在自己的国家找到宝藏。国王和 Katherine 皇后相伴十四年。劳动节假期,他们一起去电影院看了《致青春》。返程时,两人在路旁的小树林里发现一块石板,石板上写着,算出所给表达式的值,就能得到 Katharon 国最珍贵的财产。

国王和皇后请你帮忙,并答应分给你一半财产。请计算

∑i=1nim mi\sum_{i=1}^{n} i^m\,m^i

对 109+710^9+7 取模的结果。

输入格式

一行两个正整数 n,mn,m。

输出格式

一行一个整数,表示所求和式对 109+710^9+7 取模的结果。

样例

5 3
36363

数据范围

1≤n≤1091\le n\le 10^9,1≤m≤2001\le m\le 200。

题源为 Katharon #1。