baekjoon 18291

---

Idea

N = 4,
i) 1 -> 2 -> 3 -> 4
ii) 1 -> 2 -> 4
iii) 1 -> 3 -> 4
iiii) 1 -> 4

N = 5,
i) 1 -> 2 -> 3 -> 4 -> 5
ii) 1 -> 2 -> 3 -> 5
iii) 1 -> 2 -> 4 -> 5
.
.
iiiiiiii) 1 -> 8

∴

---

Code

#define _CRT_SECURE_NO_WARNINGS
#define MOD 1000000007
#include <stdio.h>

long long getResult(long long base, int power) {
	long long result = 1;
	
	while (power) {
		if (power % 2) {
			result = (result * base) % MOD;
		}
		base = (base * base) % MOD;
		power /= 2;
	}
	
	return result;
}

int main(void) {
	long long N;
	int T;

	scanf("%d", &T);

	for (int i = 0; i < T; i++) {
		scanf("%lld", &N);

		if (N < 3) {
			printf("1\n");
		}
		else {
			printf("%lld\n", getResult(2, N - 2));
		}
	}

	return 0;
}