You will be given two integers XXX and NNN, you have to calculate XNX^NXN modulo 1000000007.
The only line will have two integers XXX (0≤X≤10000000 ≤ X ≤ 10000000≤X≤1000000) and NNN (0≤N≤1090 ≤ N ≤ 10^90≤N≤109). Both XXX and NNN will not be zero at the same time.
Please write one line, the answer of the problem.
1 5
1