#P3516. 国王奇遇记加强版

    ID: 2728 传统题 1000ms 256MiB 尝试: 650 已通过: 357 难度: 6 上传者: 标签>难度分类提高构造与建模差分转化动态规划线性 DP组合数学Pascal 递推滚动数组数论模逆元快速幂费马小定理CF2000By

国王奇遇记加强版

国王奇遇记加强版

题目描述

Kanari 国王和 Katherine 皇后从电影院回宫途中,在树林里发现了一块石板。石板说,算出下列表达式就能获得 Katharon 国的宝藏。

∑i=1nimmi.\sum_{i=1}^{n} i^m m^i.

给定 n,mn,m,请计算这个和对 109+710^9+7 取模后的值。

输入格式

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

输出格式

一行一个整数,表示所求的模值。

样例 #1

5 3
36363

数据范围

1≤n≤1091\le n\le10^9,1≤m≤10001\le m\le1000。