====== 비요뜨의 징검다리 건너기 ======

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


===== 코드 =====
<dkpr py>
"""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()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_5}}