You cannot submit for this problem because the homework's deadline is due.

Description

Given \(a,b,p\), find \(a^b \bmod p\)

Format

Name your program as power.c

Input

Three integers \(a\), \(b\), and \(p\).

Output

A string in the format a^b mod p=s, where \(s=a^b \bmod p\).

Sample 1

Input

2 10 9

Output

2^10 mod 9=7

Limitation

\(0\le b,p < 2^{31}\), and \(1\le p<2^{31}\)

1s, 1024KiB for each test case.