dinamica04

#include <iostream>
#define M 123457
using namespace std;

int lgput(int n,int p)
{
	long long int a=n,P=1;
	for(int i=0;(1<<i)<=p;++i)  /// Luam toti biti lui p la rand
	{
		if(((1<<i)&p)>0) /// Daca bitul i din p este 1 atunci adaugam n^(2^i) la solutie
			P=(P*a)%M;
        a=(a*a)%M; /// Inmultim a cu a ca sa obtinem n^(2^(i+1))
	}
	return P;
}

int main()
{
    int n;
    cin>>n;
    if(n==0)
    {
        cout<<0;
        return 0;
    }
    if(n==1)
    {
        cout<<10;
        return 0;
    }
    int sol=1LL*(1LL*n*5+4)%M*lgput(5,n-1)%M;
    cout<<sol%M;
    return 0;
}