我现在要做的是：

t1 = 1, t2 = 0,MOD = 1000000007;

for i = 1:n

    t1_new = (2*(t1+t2)) % MOD;
    t2_new = t1;
    a[i] = (t1_new + t2_new) % MOD;   // where a[i] is the ith term mod p
    t1 = t1_new;
    t2 = t2_new;

return a[n]; // the required ans

但这是一个O（n）解决方案。

请只给我提示（请没有解决方案），这样我可以减少解决方案的复杂性。