Problem Statement

Pondo has two integers ~x~ and ~y~, he asks you to help him calculate ~x^y~, since this number may be large, make sure to give back the answer modulo ~10^9+7~.

Input Format

Your first and only line will contain two space-separated integers ~x~ and ~y~.

Output Format

Output ~x^y~ modulo ~10^9 + 7~.

Constraints

• ~1 \leq x, y \leq 10^9~ ## Sample Cases ### Input 1

2 10

Output 1

1024

Input 2

1000000000

Output 2

312556845

Explanation 2

Make sure to modulo by ~10^9 + 7~.