binpow-mod

//возведение в большую степень по модулю простого числа
long long mod = 1000000007;

    long long binpow(long long val, long long deg, long long mod) // рассчитывает и выводит (val^deg) % mod
    {
        if (!deg) return 1 % mod;
        if (deg & 1) return binpow(val, deg - 1, mod) * val % mod;
        long long res = binpow(val ,deg >> 1, mod);
        return (res*res) % mod;
    }