#include <iostream>
using namespace std;
int main()
{
    int n,dp[100005],a[100005],b[100005];
    cin >> n;
    dp[1]=4;
    a[1]=1;
    b[1]=1;
    for (int i=2;i<=n;i++)
    {
        dp[i]=(4*dp[i-1]-(a[i-1]+b[i-1]))%777013;
        a[i]=(a[i-1]+dp[i-1]-(a[i-1]+b[i-1]))%777013;
        b[i]=(b[i-1]+dp[i-1]-(a[i-1]+b[i-1]))%777013;
    }
    cout << dp[n];
}