#include<iostream> 
using namespace std;
class function
{
	public:
		long long f1(long long n){
			if(n==1){
				return 2;
			}
			else if(n==2){
				return 1;
			}else if(n==3){
				return 6;
			}
			else if(n<=0){
				return 0;
			}
			else
				return (this->f2(n-1))%99999999+(2*this->f1(n-3)+5)%99999999;
		}
	
		long long f2(long long n){
			if(n==1){
				return 3;
			}
			else if(n==2){
				return 4;
			}else if(n==3){
				return 5;
			}
			else if(n<=0){
				return 0;
			}
			else
				return (this->f1(n-1))%99999999+(3*this->f1(n-3))%99999999+(2*this->f2(n-3)+3)%99999999;
		}
};
int main(){
	function a;
	long long n;
	cin>>n;
	n=n%99999999;
	cout<<"f1="<<a.f1(n)<<endl;
	cout<<"f2="<<a.f2(n)<<endl;
	return 0;
}