[백준][Python] 18291 비요뜨의 징검다리 건너기

분할정복 제곱. 근데 그냥 pow써도 되는듯..

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def pow(n):
    if n<=0:
        return 1
    p_n = pow(n//2)
    if n&1:
        return p_n*p_n*2%MOD
    return p_n*p_n%MOD


MOD = int(1e9)+7
for _ in range(int(input())):
    N = int(input())
    # 2~N-1 번의 징검다리를 선택하거나 선택하지 않는 모든 경우의 수.
    print((pow(N-2))%MOD)