题目描述

王老师见小明考得这么差，就留了一道数学题，小明懵了。

题目是这样的：给定 $\red{N}$，求 $\red{1^1+2^2+3^3+\cdots+N^N}$对 $\red{10^9+7}$取模的值。

输入格式

一行一个整数 $\red{N}$。

输出格式

一行一个整数，为题目所说的答案。

样例

输入样例

3

输出样例

32

提示

$\red{1^1=1,2^2=4,3^3=27,1+4+27=32}$

对于 $\red{100\%}$的数据，$\red{1 \le N \le 10^5}$。