include<bits/stdc++.h>

using namespace std; int main(){

int n, m=99999999;
scanf("%d", &n);
long long a1=2, a2=3;
long long b1=1, b2=4;
long long c1=6, c2=5;
long long d1, d2;
if(n==1){
    printf("%lld\n%lld\n",a1%m,a2%m);
}else if(n==2){
    printf("%lld\n%lld\n",b1%m,b2%m);
}else if(n==3){
    printf("%lld\n%lld\n",c1%m,c2%m);
}else{
    for(int i=4;i<=n;i++){
        d1=(c2 + 2*a1 +5)%m;
        d2=(c1 + 3*a1 + 2*a2 +3)%m;
        a1=b1;a2=b2;
        b1=c1;b2=c2;
        c1=d1;c2=d2;
    }
    printf("%lld\n%lld\n",c1,c2);
}
return 0;

}