我们构造一个矩阵，左上角为1，右边的数为左边的数*3，下边的数为上边的数*2，那么这个矩阵的列数不会超过11，行数不会超过17

对于矩阵中的数，只要选出的两个数的位置不是四联通，就是合法的

状压一行，转移

可能有多个矩阵，即左上角不一定是1

枚举左上角，且保证这个数不被包含在其他矩阵中，那么矩阵之间就没有相同的数，互不影响，乘法原理即可

#include
     
      using namespace std;const int mod=1e9+1;int n,A[18][18],F[18][10005],line[18],vis[100005];int solve(int ST){	int M;	A[0][0]=ST;	for (M=0; A[M][0]<=n; M++) A[M+1][0]=A[M][0]*2;	for (int i=0; i
      
       >1))) F[0][i]=1;	for (int i=0; i
       
        >1)) && !(pre&now)) (F[i+1][now]+=F[i][pre])%=mod;	int ans=0;	for (int i=0; i<(1<