Lũy thừa modulo (Modular Power with For Loop)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Tính a^n lấy phần dư m bằng vòng for nhân rồi lấy dư mỗi lượt. Với n=0, trả 1%m; đặc biệt m=1 cho 0.

Input

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

Output

Số dư không âm trong [0,m-1].

Subtask

• 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.

Ví dụ

Ví dụ 1

Input

2 10 1000

Output

24

Giải thích

1024 chia 1000 dư 24.

Ví dụ 2

Input

0 0 1

Output

0

Giải thích

Tích rỗng 1, lấy dư 1 được 0.