n=int(input())
if n==1:
    print(10)
else:
    print((n*pow(5,n,123457)+4*pow(5,n-1,123457))%123457)