题目描述

计算 $x^y$ 可以采用如下代码完成

long long sum = 1;
for (int i = 1; i <= y; i++)
{
    sum = sum * x;
}

当 $y$ 是一个较大的整数，使用 for 循环计算会超时 TLE。

快速幂是一项快速计算 $x^y$ 的算法。设 $f(x,y)$ 是一个计算 $x^y$ 的函数，它的递归公式如下：

$$f(x,y)=\begin{cases} f(x,\frac{y}{2})\times f(x,\frac{y}{2}) \ \ y>0 \ 且\ y\ 是偶数\\ 1\ y=0\\ f(x,\frac{y}{2})\times f(x,\frac{y}{2})\times x \ \ y>0 \ 且\ y\ 是奇数\\ \end{cases} $$

当然除此以外快速幂还有另一种写法。请你根据上面的递归函数写出快速幂的代码。

由于答案可能很大，请你输出最终结果对 $10^9+7$ 取余的结果。

输入格式

输入两个正整数 $x,y$，$1\leq x,y\leq 10^9$

输出格式

输出 $x^y$ 对 $10^9+7$ 取余后的结果。

2 3

8