题目描述

• 小k认为快速幂还是不够快，于是想请你写一个光速幂
• 给你两个整数 $a,b$，求 $a^b \bmod 1e9+7$。

输入格式

输入只有一行两个整数，分别代表 $a,b$。

输出格式

输出一行一个字符串 a^b mod 1000000007=s，其中 $a,b$ 分别为题目给定的值， $s$ 为运算结果。

样例 #1

样例输入 #1

2 65

样例输出 #1

2^65 mod 1000000007=164688009

提示

样例解释

$2^{65} = 36893488147419103232$，$36893488147419103232 \bmod 1000000007 = 164688009$。

数据规模与约定

对于 $100\%$ 的数据，保证$0≤a,b≤10^{500000}，a+b>0$

• 提示：1000000007是质数，long long装得下 $1000000007^{2}$
• 注意时限400ms