問題文の関数は、簡単に言えば 2X2^X2X です。 高速に 2Xmod109+72^X mod 10^9+72Xmod109+7 を求めることでこの問題を解くことができます。 また、制約が小さいので下から順番に求めることもできます。