题目描述
For given integers m and n, compute mn (mod 1,000,000,007). Here, A (mod M) is the remainder when A is divided by M.
Constraints
- 1 ≤ m ≤ 100
- 1 ≤ n ≤ 109
Input
m n
Two integers m and n are given in a line.
Output
Print mn (mod 1,000,000,007) in a line.
Examples
Input
2 3
Output
8
Input
5 8
Output
390625
输入格式
见题面
输出格式
见题面
样例输入
2 3
样例输出
8