我会打表！

首先使用 $O(2^{2n})$ 的暴力跑出前几个数。

table
1  0
2  0        q      r q    r  q r
3  6        10,    0 N/A
4  60       6,    30 N/A
5  390      5,   150 N/A
6  2100     4,  1806 3, 378  N/A
7  10206    4,  5796 3, 762(*2+6)
8  46620    4, 18150 3,1530(*2+6)
9  204630   4, 55980 3,3066(*2+6)
10 874500   4,171006 3,6138(*2+6)
11 3669006  4,519156 
12 15195180

可以写出如下的 $O(n)$ 代码。

cin>>n;
if(n<3)cout<<0;
else if(n==3)cout<<6;
else if(n==4)cout<<60;
else if(n==5)cout<<390;
else if(n==6)cout<<2100;
else{
    long long bs=2100,q1=1806,q2=378;
   n-=6;
   while(n--){
      bs=bs*4+q1;
      q1=q1*3+q2;
      q2=q2*2+6;
   }
   cout<<bs;
}

对函数进行函数“套”函数。然后就想到快速幂。
$O(\log n)$ 正解出炉 !

#include<bits/stdc++.h>
using namespace std;
//a≤b≤c
//没救
//那就要求max(a,b)<a⊕b<a+b
//依旧binary
/*
table//表
1  0
2  0        q      r q    r  q r
3  6        10,    0 N/A
4  60       6,    30 N/A
5  390      5,   150 N/A
6  2100     4,  1806 3, 378  N/A
7  10206    4,  5796 3, 762(*2+6)
8  46620    4, 18150 3,1530(*2+6)
9  204630   4, 55980 3,3066(*2+6)
10 874500   4,171006 3,6138(*2+6)
11 3669006  4,519156 
12 15195180
*/
long long n,res;
/*这题估计是函数快速幂  WC过了*/
/*for q2*/long long f21=2,f20=6;
/*for q1*/long long f11=3,f10=1,f1e=0;
/*for bs*/long long f01=4,f00=1,f0e=0,f0x=0;
/*
f(q2)=f21*q2+f20
f(q1)=f11*q1+f10*q2+f1e
f(bs)=f01*bs+f00*q1+f0e*q2+f0x
*/
int main(){
//    freopen("triangle.in","r",stdin);
//    freopen("triangle.out","w",stdout);
    cin>>n;
   //无规律特判
    if(n<3)cout<<0;
    else if(n==3)cout<<6;
    else if(n==4)cout<<60;
    else if(n==5)cout<<390;
    else if(n==6)cout<<2100;
    else{
      //类似快速幂
        long long bs=2100,q1=1806,q2=378;
        n-=6;
        while(n){
         //n&1的部分和快速幂类似，套一层函数
            if(n&1)bs=(bs*f01+q1*f00+q2*f0e+f0x)%998244353;
            if(n&1)q1=(q1*f11+q2*f10+f1e)%998244353;
            if(n&1)q2=(q2*f21+f20)%998244353;
         //迭代f(bs)
            f0x=(f0x*f01+f00*f1e+f0e*f20+f0x)%998244353;
            f0e=(f0e*f01+f00*f10+f0e*f21)%998244353;
            f00=(f00*f01+f00*f11)%998244353;
            f01=f01*f01%998244353;
            //迭代f(q1)
            f1e=(f1e*f11+f10*f20+f1e)%998244353;
            f10=(f10*f11+f10*f21)%998244353;
            f11=f11*f11%998244353;
            //迭代f(q2)
            f20=(f20*f21+f20)%998244353;
            f21=f21*f21%998244353;
            n>>=1;
        }
        cout<<bs;
    }
    return 0;
}