令小J疑惑的数学题
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

听说小J对数学方面的算法比较擅长?不是吧不是吧,我咋听说他在区域赛连exgcd都看不出来呢hh
现给你小J刚刚做完的一道题,看看你会不会做
我们知道x^x是增长非常快的函数,在数学中我们管他叫幂指函数
现在我给你一个x,请你算出x^x。考虑到这个结果可能会非常大,请你对答案10^9 + 7 取模

输入描述:

一个数字x 
30%的数据(0 < x < 10^{5})
100%的数据(0 < x < 10^{18})

输出描述:

取模后的一个数字
示例1

输入

复制
2

输出

复制
4