#pragma once
#include <map>
#include <iostream>

namespace internal{
    struct PowModStruct{
        long a,b,mod;
        friend std::ostream& operator << (std::ostream& os, const internal::PowModStruct& rhs) { os << rhs.a << "^" << rhs.b << "%" << rhs.mod; return os; };
        bool operator<(const internal::PowModStruct&rhs)const{return a<rhs.a||a==rhs.a&&b<rhs.b||a==rhs.a&&b==rhs.b&&mod<rhs.mod;};
    };
}

class utils{
    utils()=delete;
    utils(utils&utils)=delete;
    static std::map<internal::PowModStruct,int>mapping;
    public:
    //a^b % mod
    static long PowMod(int a,int b,int mod);
};