찐 Even Number

최근 치토는 찐 Even Number라는 독특한 수를 정의했다. 찐 Even Number는 모든 자릿수가 $\{0, 2, 4, 6, 8\}$에 속하는 $N$자리 음이 아닌 정수이다. 다만 0 자체를 제외하고, $0246$처럼 0으로 시작하는 수는 고려하지 않는다. 예를 들어 $468$과 $660$은 찐 Even Number이지만, $14$와 $567$은 아니다.

민성이는 찐 Even Number가 궁금해져서 치토에게 $Q$개의 질문을 하려 한다. 질문의 형태는 다음과 같다.

• $N$: $N$자리 음이 아닌 정수 중 서로 다른 찐 Even Number의 개수

치토를 도와 $Q$개의 질문에 대한 답을 구해보자.

첫 번째 줄에 질문의 개수인 양의 정수 $Q$가 주어진다. $(1 \leq Q \leq 100\,000)$

두 번째 줄부터 $Q$개의 줄에 걸쳐 치토에게 물어볼 양의 정수 $N$이 주어진다. $(1 \leq N \leq 10^7)$

$Q$개의 줄에 걸쳐 치토가 답하는 수를 $10^9+7$로 나눈 나머지를 한 줄에 하나씩 출력한다.