M=1234567891
def Dem(n,k):
    p=k;res=0
    while p<=n:
        res+=n//p
        p=p*k
    return res
def LT(x, y):
    if y==0: return 1
    res=LT(x,y//2)
    res=(res*res)%M
    if y%2==1: res=(res*x%M)%M
    return res
n=int(input())
d=[0]*(n+1)
ans=1
i=2
while i*i*2<=n:
    if d[i]==0:
        j=i*i
        while j*2<=n:
            d[j]=1
            j+=i
    i+=1
i=2
while i*2<=n:
    if d[i]==0:
        ans=(ans*LT(i,Dem(n,i)//2*2)%M)%M
    i+=1
print(ans)
 

TT0xMjM0NTY3ODkxCmRlZiBEZW0obixrKToKICAgIHA9aztyZXM9MAogICAgd2hpbGUgcDw9bjoKICAgICAgICByZXMrPW4vL3AKICAgICAgICBwPXAqawogICAgcmV0dXJuIHJlcwpkZWYgTFQoeCwgeSk6CiAgICBpZiB5PT0wOiByZXR1cm4gMQogICAgcmVzPUxUKHgseS8vMikKICAgIHJlcz0ocmVzKnJlcyklTQogICAgaWYgeSUyPT0xOiByZXM9KHJlcyp4JU0pJU0KICAgIHJldHVybiByZXMKbj1pbnQoaW5wdXQoKSkKZD1bMF0qKG4rMSkKYW5zPTEKaT0yCndoaWxlIGkqaSoyPD1uOgogICAgaWYgZFtpXT09MDoKICAgICAgICBqPWkqaQogICAgICAgIHdoaWxlIGoqMjw9bjoKICAgICAgICAgICAgZFtqXT0xCiAgICAgICAgICAgIGorPWkKICAgIGkrPTEKaT0yCndoaWxlIGkqMjw9bjoKICAgIGlmIGRbaV09PTA6CiAgICAgICAgYW5zPShhbnMqTFQoaSxEZW0obixpKS8vMioyKSVNKSVNCiAgICBpKz0xCnByaW50KGFucykK