public class Euler980 {
    static final long MOD = 888888883L;
    static final long MUL = 8888L;
    static final long A0 = 88888888L;

    static long computeF(int N) {
        long[][] cnt = new long[8][2];

        long a = A0;

        for (int i = 0; i < N; ++i) {
            int px = 0, py = 0, pz = 0;
            int inv = 0;

            for (int k = 0; k < 50; ++k) {
                int b = (int) (a % 3L);
                if (b == 0) {
                    inv ^= (py ^ pz);
                    px ^= 1;
                } else if (b == 1) {
                    inv ^= pz;
                    py ^= 1;
                } else {
                    pz ^= 1;
                }
                a = (a * MUL) % MOD;
            }

            int mask = (px << 2) | (py << 1) | pz;
            cnt[mask][inv]++;
        }

        long total = 0;
        for (int mask = 0; mask < 8; ++mask) {
            long c0 = cnt[mask][0];
            long c1 = cnt[mask][1];
            if (mask == 0) {
                total += c0 * c0 + c1 * c1;
            } else {
                total += 2L * c0 * c1;
            }
        }
        return total;
    }

    public static String solve() {
        return Long.toString(computeF(1000000));
    }

    public static void main(String[] args) {
        if (computeF(10) != 13 || computeF(100) != 1224) {
            System.err.println("Validation failed");
            return;
        }
        System.out.println(solve());
    }
}