原题为单组测试，我们增加一组多测的数据。

时间限制： 1.0 秒

空间限制： 512 MB

题目描述

每个同学在这一学期各自会有 $n$ 次考试，考试科目有 4 种，分别为计原、网原、信原和操统。

每一次考哪一科是不定的，但通过总结以往考试经验，发现了这样几个规律：

1. 如果这次考的是计原，那么下一次一定会考网原；
2. 如果这次考的是信原，那么下一次一定会考操统；
3. 如果这次考的是网原，那么下一次要么考计原，要么考操统；
4. 如果这次考的是操统，那么下一次要么考网原，要么考信原。

已经知道，本学期所有同学的第一次考试科目都是计原，他们每个人都打算拟定一个可以应对所有可能情况的应考复习计划。请对他们每个人分别回答，整个学期有多少种可能的考试科目安排满足以上规律。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $T$，表示共有 $T$ 组数据。

接下来 $T$ 行，每组数据占一行，分别包含一个正整数 $n$，代表本学期总的考试次数。输入数据保证 $n\le 10^4$。

输出格式

输出到标准输出。

共输出 $T$ 行，第 $i$ 行对应第 $i$ 组询问所求的答案。每行一个正整数，表示符合规律的科目安排方案的总数。考虑到这个结果可能会很大，因此你只需要输出它对 $7654321$ 取模的值即可。

1
5

5

3
1145
1919
810

3205712
7598018
396910

子任务

• 子任务 1（97 分）：所有数据保证 $T=1,n\le 10^4$；
• 子任务 2（3 分）：所有数据保证 $T=10^4,n\le 10^4$。