快速幂练习

题目描述

给你两个数 $a$ 和 $n$，你需要求出 $a$ 的 $n$ 次方模 $10^9 + 7$ 的值。

输入格式

一行两个整数 $a$ 和 $n$。

输出格式

一个正整数表示答案。

样例输入

5 10000

样例输出

378321089

数据范围

对于 $100\%$ 的数据，保证 $1\leq a, n\leq 10^9$。