AC

include<bits/stdc++.h>

using namespace std; const int MOD=99999999; int main(){

    int n;
    cin>>n;
    if(n==1){
        cout<<2%MOD<<endl<<3%MOD<<endl;
        return 0;
    }else if(n==2){
        cout<<1%MOD<<endl<<4%MOD<<endl;
        return 0;
    }else if(n==3){
        cout<<6%MOD<<endl<<5%MOD<<endl;
        return 0;
    }
    int a1=2,b1=3,a2=1,b2=4,a3=6,b3=5;
    for(int i=4;i<=n;i++){
        int ca=(b3+2*a1+5)%MOD;
        int cb=(a3+3*a1+2*b1+3)%MOD;
        a1=a2;b1=b2;a2=a3;b2=b3;a3=ca;b3=cb;
    }
    cout<<a3<<endl<<b3<<endl;
    return 0;

}