U414149 考试

**时间限制：** 1.0 秒 **空间限制：** 512 MB 注：本题数据的输入输出格式与原题进行了微调，将一组输入改成多组输入。我们有 10 个计入分数的测试点（每个测试点 10 分）以及 1 个不计入分数的测试点，只通过前 10 个测试点视为 100 分 `unaccepted` ，通过所有测试点视为 `accepted` 。此外，我们还为原题完善了部分分的数据范围。

每个同学在这一学期各自会有 $n$ 次考试，考试科目有 4 种，分别为计原、网原、信原和操统。 每一次考哪一科是不定的，但通过总结以往考试经验，发现了这样几个规律： 1. 如果这次考的是计原，那么下一次一定会考网原； 2. 如果这次考的是信原，那么下一次一定会考操统； 3. 如果这次考的是网原，那么下一次要么考计原，要么考操统； 4. 如果这次考的是操统，那么下一次要么考网原，要么考信原。 已经知道，本学期所有同学的第一次考试科目都是计原，他们每个人都打算拟定一个可以应对所有可能情况的应考复习计划。请对他们每个人分别回答，整个学期有多少种可能的考试科目安排满足以上规律。

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

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

### 数据范围 本题分两个 subtask，每个 subtask 内部采用传统计分方式。 subtask 1 : 每个测试点 10 分，所有数据保证 $T=1$ 。对于其中 $40\%$ 的数据，保证 $n\le 40$ 。对于 $100\%$ 的数据，保证 $n\le 10^4$ 。 subtask 2 : 测试点 0 分，数据有 $T=10^4, n\le 10^4$ 。