T组，每组给出一个，求 

矩阵快速幂，由第N个状态到第N+1个状态，推出关系矩阵，然后关系矩阵快速幂，再乘以出事矩阵就好了。

由于的最高项为立方，所以需要加上平方项和一次方项和零次方项

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 123456789;
ll len = 6;
struct node
{
	ll matrix[6][6];
	node()
	{
		memset(matrix, 0, sizeof matrix);
	}
	void set(ll a[6][6])
	{
		for (int i = 0; i < len; i++)
		{
			for (int j = 0; j < len; j++)
				matrix[i][j] = a[i][j];
		}
	}
	void one()
	{
		for (int i = 0; i < len; i++)
			matrix[i][i] = 1;
	}
	node operator * (node other)
	{
		node ans;
		for (int i = 0; i < len; i++)
		{
			for (int j = 0; j < len; j++)
			{
				for (int k = 0; k < len; k++)
				{
					ans.matrix[i][j] += matrix[i][k] * other.matrix[k][j] % mod;
					ans.matrix[i][j] %= mod;
				}
			}
		}
		return ans;
	}
};
node power(node a, ll b)
{
	node res;
	res.one();
	while (b)
	{
		if (b & 1)
			res = res * a;
		a = a * a;
		b >>= 1;
	}
	return res;
}
int main()
{
	//中间矩阵
	ll change[6][6] = {
		{0,1,0,0,0,0},
		{2,1,1,0,0,0},
		{0,0,1,3,3,1},
		{0,0,0,1,2,1},
		{0,0,0,0,1,1},
		{0,0,0,0,0,1},
	};
	//初始矩阵
	ll pre[6][6]={
		{1,0,0,0,0,0},
		{2,0,0,0,0,0},
		{27,0,0,0,0,0},
		{9,0,0,0,0,0},
		{3,0,0,0,0,0},
		{1,0,0,0,0,0},
	};
	node real;
	real.set(pre);
	node temp;
	temp.set(change);

	node q1 = power(temp, 1);
	node q2 = power(temp, 2);
	node q3 = power(temp, 3);

	int t;
	scanf("%d", &t);
	while (t--)
	{
		ll n;
		scanf("%lld", &n);
		node ans = power(temp, n - 1) * real;
		printf("%lld\n", ans.matrix[0][0]);
	}
}