Given two integers x and y, compute x^y modulo 1,000,000,007 (that is, 10⁹ + 7).

Input

A single line containing two space-separated integers x (0 ≤ x ≤ 10¹⁸) and y (0 ≤ y ≤ 10¹⁸).

Output

A single integer x^y mod(10⁹ + 7).

Note

• Subtask 1 (20 pts): 1 ≤ x and y ≤ 10⁶.
• Subtask 2 (30 pts): 1 ≤ x (no bound on y beyond the above).
• Subtask 3 (50 pts): no additional constraints.

Example

2 3

8