#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int N=,P=;

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,m=;

int inv[N],fac[N],facInv[N];

void ini(){

    inv[]=;fac[]=facInv[]=;

    for(int i=;i<=n;i++){

        if(i!=) inv[i]=-P/i*inv[P%i]%P;

        if(inv[i]<) inv[i]+=P;

        fac[i]=fac[i-]*i%P;

        facInv[i]=facInv[i-]*inv[i]%P;

    }

}

int L[N],tot;

int sum,ans;

inline int gcd(int a,int b){return b== ? a : gcd(b,a%b);}

inline int Pow(int a,int b){

    int re=;

    for(;b;b>>=,a=a*a%P)

        if(b&) re=re*a%P;

    return re;

}

inline void mod(int &x){if(x>=P) x-=P;}

void dfs(int d,int now){

    if(d==n){

        int lo=;

        int cnt=fac[n],same=;

        sort(L+,L++tot);

        for(int i=;i<=tot;i++){

            lo+=L[i]/;

            for(int j=i+;j<=tot;j++) lo+=gcd(L[i],L[j]);

            cnt=cnt*inv[L[i]]%P;

            if(i!=&&L[i]==L[i-]) same++;

            else if(same!=) cnt=cnt*facInv[same]%P,same=;

        }

        if(same!=) cnt=cnt*facInv[same]%P;

        mod(sum+=cnt);

        mod(ans+=cnt%P*Pow(m,lo)%P);

    }else{

        for(int j=now;d+j<=n;j++){

            L[++tot]=j;

            dfs(d+j,j);

            tot--;

        }

    }

}

int main(){

    //freopen("in","r",stdin);

    n=read();

    ini();

    dfs(,);

    ans=ans*Pow(sum,P-)%P;

    printf("%d",ans);

}