#include "utils.h"
#include <cmath>

std::map<internal::PowModStruct,int>utils::mapping;

long utils::PowMod(int a,int b, int mod){
    int shift=0;
    long product=0;
    for(long n=1;n<=b;n*=2){
        if(utils::mapping.find({a,n,mod})!=utils::mapping.end()){
            if(b&n){
                if(product==0){
                    product=1;
                }
                std::cout<<utils::mapping[{a,n,mod}]<<std::endl;
                product*=utils::mapping[{a,n,mod}];
                product%=mod;
            }
            continue;
        }
        if(n==1){
            utils::mapping[{a,n,mod}]=a%mod;
        }else{
            utils::mapping[{a,n,mod}]=long(utils::mapping[{a,n/2,mod}])*utils::mapping[{a,n/2,mod}]%mod;
        }
        if(b&n){
            if(product==0){
                product=1;
            }
            product*=utils::mapping[{a,n,mod}];
            product%=mod;
        }
        shift++;
    }
    return product%mod;
}