TUMSO18: EZ Problem

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

const int logN = log2(1e18);
const int MD = 1e9 + 7;

int blift[logN + 1];

int modExp(int base, lli exp){
    blift[0] = base % MD;
    for(int e = 1; e <= logN; ++e){
        blift[e] = ((lli)blift[e - 1] * blift[e - 1]) % MD;
    }
    int ans = 1;
    for(int e = logN; e >= 0; --e){
        if(exp >= ((lli)1 << e)){
            ans = ((lli)ans * blift[e]) % MD;
            exp -= ((lli)1 << e);
        }
    }
    return ans;
}

int main(){

    int Q;
    scanf("%d", &Q);
    while(Q--){
        lli n;
        int a;
        scanf("%lld%d", &n, &a);
        if(n == 0){
            cout << "0\n";
            continue;
        }
        int part1 = modExp(a + a, n - 1);
        int part2 = (MD + (lli)part1 * (a + a) - 1) % MD;
        int part3 = modExp(a + a - 1, MD - 2);
        cout << (((lli)part1 * part2) % MD * part3) % MD << '\n';
    }

    return 0;
}