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;
}