Tichpx dạy học phần "An toàn và bảo mật thông tin" với rất nhiều các lý thuyết toán như

• Lý thuyết số học
• Lý thuyết đồng dư (modulo)
• Lý thuyết trường hữu hạn

Trong đó có bài toán lũy thừa số lớn, cho hai số nguyên dương a và b có tới ${10}^5$ chữ số, cần phải tính $a^b$. Bạn hãy giúp Tichpx lập trình tính giá trị lũy thừa đó nhé nhưng kết quả ra có thể là một số rất lớn bạn chỉ cần in ra phần dư của kết quả chia cho ${10}^9+7$

Input

• Dòng đầu là thừa số a là một số nguyên dương có không quá ${10}^5$ chữ số
• Dòng thứ hai là số mũ b cũng là một số nguyên dương có không quá ${10}^5$ chữ số

Output

Một số nguyên không âm là kết quả của bài toán

Ví dụ 1

Input

2
10

Output

1024

Ví dụ 2

Input

252423480283585327589234785723489579234759234758924335
8252345823497983427592347589234759823479592349858923475924783959823479857923478592347543

Output

966464554