Statement

Bob has to send a secret code 5 to his boss. He designs a method to encrypt the code using two key values N and M. The formula that he uses to develop the encrypted code is shown below:

(((S^N % 10)^M)%1000000007)

Input Format

The input consists of an integer secretCode, representing the secret code (S).

The second line consists of an integer firstkey, representing the first key value (N)

The third line consists of an integer secondkey, representing the second key value (M).

Output

Print an integer representing thecode encrypted by Bob.

Example

Input:

2
3
4

Output:

4096

Explanation

S=2 , N=3 , M = 4 and the formula of the encrypted code is: (((S^N % 10)^M)%1000000007) ((2^3 % 10)^3)%1000000007) = 4096

Solution

To edit the code click here