用 853 打打表。。

PE854.cpp

#include <lastweapon/io>
#include <lastweapon/bignum>
using namespace lastweapon;



const int N = 500000+1;//1000001;
bignum f[N];

bignum gcd(bignum a, bignum b) {
    return b == 0 ? a : gcd(b, a % b);
}

LL a[N];

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

    //REP_1(i, 120) cout << a(i) << endl;
    //sieve();
    //cout << z << endl;
    /*map<int, int> M;
    REP_1(i, 1000) M[a(i)] = i;
    int P = 1; REP_1(i, 40) {
        if (!CTN(M, i)) M[i] = 1;
        P *= M[i];
        cout << M[i] << " ";
    }
    cout << endl;
    cout << P << endl;*/

    // https://oeis.org/A210209

    /*MOD = 1234567891;
    bignum P = 2; f[0] = 0, f[1] = 1;
    FOR(i, 2, N) {
        f[i] = f[i-1] + f[i-2];
        if (i % 100000 == 0) {
            cout << i << ": " << endl;
            //cout << f[i] << endl;
        }
        if (i & 1) {
            P *= gcd(f[i]-1, f[i-1]);
            P %= MOD;
        }
    }
    cout << P << endl;
    //cout << f[N] << endl;*/

    // https://oeis.org/A005013
    LL P = 8;
    MOD = 1234567891;
    cout << MOD << endl;
    a[0] = 0; a[1] = 1; a[2] = 1; a[3] = 4;
    FOR(i, 4, N) {
        a[i] = 3LL*a[i-2] - a[i-4];
        a[i] %= MOD; if (a[i] < MOD) a[i] += MOD;
        //cout << a[i] << endl;
        P *= a[i]; P %= MOD;
    }
    cout << P << endl;

}