想定解

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