Modular exponentiation P29212


Statement
 

pdf   zip

html

Write a program that, given n, k and m, computes nk modm.

Input

Input consists of several cases, each one with three natural numbers n, k and m. Assume 2 ≤ n ≤ 30000 and 2 ≤ m ≤ 30000.

Output

For every case, print nk modm.

Public test cases

  • Input

    2 10 10000
2 10 2
7 1000000 29999
7 1000000 30000
30000 1000000000 29876

    Output

    1024
0
7959
1
5336
    • Information
    Author
    Pol Mauri
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++ Python
    User solutions
    C++ Python