I am trying to solve this problem in Python. Noting that only the first kiss requires the alternation, any kiss that is not a part of the chain due to the first kiss can very well have a hug on the 2nd next person, this is the code I have come up with. This is just a simple mathematical calculation, no looping, no iteration, nothing. But still I am getting a timed-out message. Any means to optimize it?

import psyco
psyco.full()
testcase = int(raw_input())
for i in xrange(0,testcase):
    n = int(raw_input())
    if n%2:
        m = n/2;
        ans = 2 + 4*(2**m-1);
        ans = ans%1000000007;
        print ans
    else:
        m = n/2 - 1
        ans = 2 + 2**(n/2) + 4*(2**m-1);
        ans = ans%1000000007
        print ans