import java.util.*;

public class Euler940 {
    static final long kMod = 1123581313L;

    static long[][] matMul(long[][] a, long[][] b) {
        long[][] c = new long[2][2];
        for (int i = 0; i < 2; ++i) {
            for (int k = 0; k < 2; ++k) {
                if (a[i][k] == 0)
                    continue;
                for (int j = 0; j < 2; ++j) {
                    c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % kMod;
                }
            }
        }
        return c;
    }

    static long[][] matPow(long[][] base, long exp) {
        long[][] res = { { 1, 0 }, { 0, 1 } };
        long[][] b = { { base[0][0], base[0][1] }, { base[1][0], base[1][1] } };
        while (exp > 0) {
            if ((exp & 1) != 0) {
                res = matMul(res, b);
            }
            b = matMul(b, b);
            exp >>= 1;
        }
        return res;
    }

    static long[] matVecMul(long[][] a, long[] v) {
        long[] r = new long[2];
        for (int i = 0; i < 2; ++i) {
            r[i] = (a[i][0] * v[0] + a[i][1] * v[1]) % kMod;
        }
        return r;
    }

    public static String solve(int k) {
        long[] fib = new long[k + 1];
        fib[0] = 0;
        if (k >= 1)
            fib[1] = 1;
        for (int i = 2; i <= k; ++i) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }

        long[][] C = { { 0, 1 }, { 3, 1 } };
        long[][] M = { { 1, 1 }, { 3, 2 } };
        long[] v0 = { 0, 1 };

        long[][] col = new long[k + 1][2];
        long[][][] row = new long[k + 1][2][2];

        for (int i = 2; i <= k; ++i) {
            row[i] = matPow(M, fib[i]);
            col[i] = matVecMul(matPow(C, fib[i]), v0);
        }

        long ans = 0;
        for (int i = 2; i <= k; ++i) {
            for (int j = 2; j <= k; ++j) {
                long val = (row[i][0][0] * col[j][0] + row[i][0][1] * col[j][1]) % kMod;
                ans = (ans + val) % kMod;
            }
        }
        return Long.toString(ans);
    }

    public static void main(String[] args) {
        System.out.println(solve(50));
    }
}