비요뜨의 징검다리 건너기

• 1번과 N번 사이에 있는 징검다리를 원하는 만큼 밟고 갈수 있다.
• 따라서 {2, … ,N-1}의 부분집합의 갯수를 구하는 문제가 된다. 답은 2^(N-2) % MOD. 거듭제곱의 빠른 계산 (Exponentiation by squaring)을 이용하면 O(logN)에 구할수 있다.
  • N=1일때에는 1을 출력하는 것만 신경써주면 된다

"""Solution code for "BOJ 18291. 비요뜨의 징검다리 건너기".

- Problem link: https://www.acmicpc.net/problem/18291
- Solution link: http://www.teferi.net/ps/problems/boj/18291
"""

import sys

MOD = 10**9 + 7


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        N = int(sys.stdin.readline())
        print(1 if N == 1 else pow(2, N - 2, MOD))


if __name__ == '__main__':
    main()