思路

首位不能0，偶数个3包括0个3，首位8/1初始化，随后9/1递推取模。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;int even=8,odd=1;for(int i=1;i<n;i++){int x=(even*9+odd)%12345,y=(odd*9+even)%12345;even=x;odd=y;}cout<<even<<'\n';}