按照题意递推即可。

f[i,j]表示处理到第i门，并且第i门考的是j科目的方案数。
j=1 政治 -> 历史

j=2 综合 -> 地理
j=3 历史 -> 政治/地理
j=4 地理 -> 历史/综合
边界：f[1,1]=1,其他为0
目标：f[n,1]+f[n,2]+f[n,3]+f[n,4]

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=10000+5;
const int INF=0x3f3f3f3f;
const int mod=7654321;
int f[maxn][6]; 
int n,ans=0;
/*
f[i,j]表示处理到第i门，并且第i门考的是j科目的方案数。
j=1 政治 -> 历史  
j=2 综合 -> 地理 
j=3 历史 -> 政治/地理 
j=4 地理 -> 历史/综合 
边界：f[1,1]=1,其他为0
目标：f[n,1]+f[n,2]+f[n,3]+f[n,4] 
*/
void dp(){
    f[1][1]=1;
    for(int i=1;i<=n-1;i++){
        f[i+1][3]=(f[i+1][3]+f[i][1])%mod;
        f[i+1][4]=(f[i+1][4]+f[i][2])%mod;  
        f[i+1][1]=(f[i+1][1]+f[i][3])%mod;
        f[i+1][4]=(f[i+1][4]+f[i][3])%mod;
        f[i+1][3]=(f[i+1][3]+f[i][4])%mod;
        f[i+1][2]=(f[i+1][2]+f[i][4])%mod;
    }
    for(int j=1;j<=4;j++) ans=(ans+f[n][j])%mod;
}
int main() {
    ios::sync_with_stdio(false);
    //freopen("文科生的悲哀.in","r",stdin);
    cin>>n;
    dp();
    cout<<ans;
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif