Modular Power with For Loop

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Compute a^n modulo m using for-loop modular multiplication. For n=0, use 1%m; m=1 yields zero.

Input

0<=a<=1000, 0<=n<=1000, 1<=m<=1000000.

Output

The nonnegative remainder in [0,m-1].

Subtasks

• Subtask 1 (20%): a<=10,n<=10,m<=10.
• Subtask 2 (30%): a<=100,n<=100,m<=1000.
• Subtask 3 (50%): a<=1000,n<=1000,m<=1000000.

Examples

Example 1

Input

2 10 1000

Output

24

Explanation

1024 modulo 1000 is 24.

Example 2

Input

0 0 1

Output

0

Explanation

The empty product 1 modulo 1 is zero.