题目描述

壮族是一个善舞的民族，青少年们经常聚在一起跳舞。现在南宁当地社区组织了一场舞蹈比赛，每位参赛者需要表演一段舞蹈，并根据评委的打分来决定胜负。评委打分的规则是：每位评委给出一个整数 $a$，主办方根据评委给出的另一个整数 $b$，计算 $a$ 的 $b$ 次方，并将结果对 $1000000007$ 取模，最后得到的数值就是该评委的最终打分。津津、菲菲和皮皮准备编写一个程序帮助主办方更快地得出分数。

输入格式

一行两个整数 $a$，$b$。

输出格式

一行一个整数表示 $a$ 的 $b$ 次方模 $10^9+7$ 的结果

样例

输入#1

135 998776

输出#1

44954590

数据范围与提示

$a,b \leq 10^9$