#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
typedef long long ll;
const int N = 55;
const int Fuck=95041567;
using namespace std;

int pri[]={31,37,41,43,47};
int nn,m,n;
int b[N][N];
ll ans[10];

void init(int p){
    b[1][1]=1;
    b[2][1]=1,b[2][2]=2;
    for(int i=3;i<50;i++){
        b[i][1]=b[i-1][i-1];
        for(int j=2;j<=i;j++){
            b[i][j]=(b[i-1][j-1]+b[i][j-1])%p;
        }
    }
//    for(int i=1;i<50;i++){
//        for(int j=1;j<=i;j++) printf("%d ",b[i][j]);
//        puts("");
//    }
}

struct Mat{
    int val[N][N];
    void unit() {
        zero();
        for (int i=0; i<N; i++) val[i][i]=1;
    }
    void zero() {
        memset(val,0,sizeof(val));
    }
};

Mat operator *(const Mat &a,const Mat &b) {
    Mat tmp;
    tmp.zero();
    for (int k=1; k<=nn; k++) {
        for (int i=1; i<=nn; i++) {
            if (a.val[i][k]) {
                for (int j=1; j<=nn; j++) {
                    tmp.val[i][j]+=(a.val[i][k]*b.val[k][j])%m;
                    if (tmp.val[i][j]>=m) tmp.val[i][j]%=m;
                }
            }
        }
    }
    return tmp;
}

Mat operator ^(Mat x,int n) {
    Mat tmp;
    tmp.unit();
    while (n) {
        if (n&1) tmp=tmp*x;
        x=x*x;
        n>>=1;
    }
    return tmp;
}


void Gcd(ll a,ll b,ll &d,ll &x,ll &y) {
    if (!b) {
        d=a,x=1,y=0;
    }else {
        Gcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}

ll inv(ll a,ll b,ll n, ll &d) {
    ll x,y;
    Gcd(a,n,d,x,y);
    if (b%d) return -1;
    return ((x*b/d)%n+n)%n;
}

ll getans() {
    ll m1,m2,a1,a2,x,d;
    m1=pri[0];
    a1=ans[0];
    bool flag=false;
    for (int i=1; i<5; i++) {
        if (flag) continue;
        m2=pri[i],a2=ans[i];
        x=inv(m1,a2-a1,m2,d);
        if (x==-1) {flag=true; continue;}
        a1=m1*x+a1;
//        printf("%lld ",a1);
        m1=m1*m2/d;
        a1=(a1%m1+m1)%m1;
    }
 //   puts("");
    if (flag) a1=-1;
//    return a1;
    return (a1%Fuck+Fuck)%Fuck;
}

ll solve(int n,int p){
    m=p,nn=p+1;
    Mat tmd;
    tmd.zero();
    for(int i=1;i<=p;i++){
        tmd.val[i][i+1]=1;
    }
    tmd.val[p+1][1]=1,tmd.val[p+1][2]=1;
    init(p);
    Mat res;
    res.zero();
    for(int i=1;i<=p+1;i++){
        res.val[i][1]=b[i][i];
    }
    res=(tmd^(n-1))*res;
    return res.val[1][1];
}

int main(){
//    init(47);
//    freopen("in","r",stdin);
    int T;
//    scanf("%d",&T);
    while (1) {
        scanf("%d",&n);
        for (int i=0; i<5; i++) {
            ans[i]=solve(n,pri[i]);
            cout<<ans[i]<<" ";
        }
        cout<<endl;
        ll res=getans();
        cout<<res<<endl;
    }
    return 0;
}