def listRozkladu(mocnina):
    vysledok=[]
    x=mocnina
    while(x>=1):
        l=1
        while(2*l<=x):
            l=2*l
        vysledok.insert(0,l)
        x=x-l
    return vysledok
def vypis(a,m,rozsah):
    mocniny=listRozkladu(rozsah)
    k=0;
    priebezne=a
    l=1
    priebeznyVysledok=1
    vysledky=[]
    while(l<=rozsah):
        
        print(a, "^",l," = ", priebezne)
        k=k+1;
        
        
        if l in mocniny:
            priebeznyVysledok=(priebeznyVysledok*priebezne)%m
            vysledky.append(priebezne)
        priebezne= (priebezne*priebezne)%m
        l=l*2
    for i in mocniny:
        print("(",a,"^",i,")",end = '')
        if i!=mocniny[-1] :
            print(" * ",end='')
    print("=",end='')
    for i in vysledky:
        print(i,end = '')
        if i!=vysledky[-1]:
            print("*",end='')
    print("=",priebeznyVysledok)
    
def main():

    m = int(input("zadaj modul:"))
    a = int(input("zadaj mocnene cislo:"))
    rozsah = int(input("zadaj mocninu:"))
    vypis(a,m,rozsah)
    #print(listRozkladu(rozsah))
    #v=(a**rozsah)%m
    #print(v)
    



if __name__ == '__main__':
    main()