Modular exponentiation P29212


Statement
 

pdf   zip

thehtml

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