/* cup14-64.c by Hiroki Sumida-Takahashi 2022, July 7 */

#include <stdio.h>

unsigned long long int modpow(unsigned long long int a, unsigned long long int b, unsigned long long int m);

void main()
 {
  unsigned long long int p,k,maxp=10000,d,u,ty,q1=maxp/2,q2=maxp/4,n,kkk,im,jm,d12,ad;
  unsigned long long int i,j,jj,djj,dd,d1,d2,qq,minval,i1,i2,i1m,i2m,tmp,tmpp,tmppp,a,sa;
  unsigned long long int tmp0,tmp1,tmp2,tmp3,tmp4,tmp0d,tmp1d,tmp2d,tmp3d,tmp4d;
  unsigned long long int inv[maxp];
  unsigned long long int rel[q1];
  unsigned long long int rel1[q1];
  unsigned long long int rel4[q1];
  unsigned long long int sm[q1];
  unsigned int e[q1][q2];
  unsigned long long int vr[q1];
  unsigned long long int vrw[q1];
  unsigned long long int wr[q1];
  unsigned long long int wrw[q1];
  unsigned long long int sg[q1];
  unsigned long long int dl[q1]; 
  FILE *file0,*file1,*file2,*file4;

  file0=fopen("bcn3.txt","r");
  file1=fopen("relation3x.txt","w");
  file4=fopen("relation3w.txt","w");
  
while(fscanf(file0,"%lld %lld %lld %lld %lld\n",&p,&k,&d,&u,&ty)!=EOF)
  {
  if((p>maxp-1000)&&(p<maxp))
    {

     inv[0]=0;
     for (i=1;i<p;i++)
       {
        inv[i]=modpow(i,p-2,p);
       }


/* 1-part  */

     for (j=0;j<(p-1)/2;j++)
       {
         tmp=((2*p-k-2*j)%(p-1))/2;
         dl[j]=tmp;

         if (j<tmp)
           {
            sg[j]=1;
            sg[tmp]=0;       
           }
         if (j==tmp)
           {
            sg[j]=1;
           }
         if (j>tmp)
           {
            sg[j]=0;
            sg[tmp]=1;       
           }
       }

     d1=(p-3)/2;
     d2=0;
     for (j=0;j<(p-1)/2;j++)
       {
        if (sg[j]==1)
          {
           wr[d2]=j;
           d2++;
          }
       }
     d2=d2-1;
 
     for (j=0;j<d2+1;j++)
       {
        wrw[wr[j]]=j;
       }

     for (j=0;j<d2+1;j++)
       {
        vr[j]=j;
       }

     for (i=0;i<d1+1;i++)
       {
        for (j=0;j<d2+1;j++)
          {
           e[i][j]=0;
          }
       }
     for (i=0;i<d1+1;i++)
       {
        a=2*i+3;
        for (j=0;j<(p-1)/2;j++)
          {
           jj=2*j;
           djj=(2*p-k-jj)%(p-1);
           tmp=(p+1+modpow(a,jj,p)-modpow(2,jj,p))%p;
           tmp=(tmp*(p+1-modpow(2,djj,p)))%p;
           tmp=(tmp*(p+1-modpow(a-1,djj,p)))%p;
           if (sg[j]==1)
             {   
              e[i][wrw[j]]=(e[i][wrw[j]]+tmp)%p;
             }
           else
             {
              e[i][wrw[dl[j]]]=(p+e[i][wrw[dl[j]]]-tmp)%p;
             }
          }
       }

     minval=1;
     i=0;
     while((minval!=0)&&(i<d2+1))
       {
        minval=0;
        i2=i;
        while((minval==0)&&(i2<d2+1)) 
          {     
           i1=i;
           while((minval==0)&&(i1<d1+1))
             {
              if (e[i1][i2]%p!=0)
                {
                 i1m=i1;
                 i2m=i2;
                 minval=1;
                }
              i1++;
             }
           i2++; 
          }
        if (minval!=0)
          {
           if (i!=i1m)
             {
              for (i2=0;i2<d2+1;i2++)
                {
                 tmp=e[i][i2];
                 e[i][i2]=e[i1m][i2];
                 e[i1m][i2]=tmp;
                }
              }
            if (i!=i2m)
              {
               for (i1=0;i1<d1+1;i1++)   
                 {     
                  tmp=e[i1][i];
                  e[i1][i]=e[i1][i2m];
                  e[i1][i2m]=tmp;
                 }
              }
            tmp=vr[i];
            vr[i]=vr[i2m];
            vr[i2m]=tmp;

            tmp=e[i][i];
            tmp=inv[tmp];
            for (i1=i+1;i1<d1+1;i1++)
              {
               tmpp=(e[i1][i]*tmp)%p;
               for (i2=i;i2<d2+1;i2++)
                 {
                  tmppp=(p+e[i1][i2]-((tmpp*e[i][i2])%p))%p;
                  e[i1][i2]=tmppp;
                 }
              }
          }/*if minval!=0 */
          i++;
       }/*while i*/

   for (j=0;j<d2+1;j++)
     {
      vrw[vr[j]]=j;   
     }
 
   im=0;
   while(e[im][im]!=0)
     {
      im++;
     }
   
   jm=q1;
   j=im;
   while((jm==q1)&&(j<d2+1))
     { 
     i=0;
     while((jm==q1)&&(i<im))
       {
        if (e[i][j]!=0)
          {
           jm=j;
          } 
          i++;
       }
     j++;
     }    

   fprintf(file1,"%lld %lld %lld %lld \n",p,k,im,jm);

   if ((im!=jm)||(im!=d2))
     {
       printf("+++\n");
       fprintf(file1,"+++\n");
     }


   rel[jm]=1;
   tmp=0;
   j=im;
   while(tmp!=1) 
    {
    j--;
    rel[j]=0;
    for (i2=j+1;i2<d2+1;i2++)
      {
      rel[j]=(p+rel[j]-(e[j][i2]*rel[i2])%p)%p;
      }
    rel[j]=(inv[e[j][j]]*rel[j])%p;
    if (j==0)
      {
       tmp=1;
      }
    }

   if (rel[vrw[0]]!=0)
     {
     tmp=inv[rel[vrw[0]]];
     for (j=0;j<d2+1;j++)
       {
        rel[j]=(tmp*rel[j])%p;
       }
     }
   else
     {
      fprintf(file1,"***\n");
     }   

   for (j=0;j<(p-1)/2;j++)
     {
     if (sg[j]==1)
       {
        rel1[j]=rel[vrw[wrw[j]]];
       }
     else
       {
        rel1[j]=(p-rel[vrw[wrw[dl[j]]]])%p;
       }
       fprintf(file1,"%lld ",rel1[j]);
     } 
   fprintf(file1,"\n");


/* 4-part  */

   d1=(p-1)/2;

   for (j=0;j<(p-1)/2;j++)
     {
     tmp=((2*p-k-2*j-2)%(p-1))/2;
     dl[j]=tmp;

     if (j<tmp)
       {
        sg[j]=1;
        sg[tmp]=0;       
       }
     if (j==tmp)
       {
        sg[j]=1;
       }
     if (j>tmp)
       {
        sg[j]=0;
        sg[tmp]=1;       
       }
     }

    d2=0;
    for (j=0;j<(p-1)/2;j++)
      {
      if (sg[j]==1)
        {
          wr[d2]=j;
          d2++;
         }
        }
      d2=d2-1;

      for (j=0;j<d2+1;j++)
        {
         wrw[wr[j]]=j;
        }

      for (i=0;i<d1+1;i++)
        {
        for (j=0;j<d2+2;j++)
          { 
           e[i][j]=0;
          }
        }

      for (j=0;j<d2+1;j++)
        {
         vr[j]=j;
        }

      for (i=0;i<d1+1;i++)
        {
        a=2*i+1;
        if ((a%p!=0)&&((a-1)%p!=0))
          {
          for (j=0;j<(p-1)/2;j++)
            {
             jj=2*j+1;
             if (a%4==1)
               {
                sa=1;
                }
             else
               {
                sa=p-1;
               }
             tmp=(p+1-(sa*modpow(a%p,jj,p))%p)%p;
             if (sg[j]==1)
               {   
                e[i][wrw[j]]=(e[i][wrw[j]]+tmp)%p;
               }
             else
              {
            e[i][wrw[dl[j]]]=(p+e[i][wrw[dl[j]]]-tmp)%p;
              }
            }/* for j*/
          }/* if a*/
        }/* for i*/

    for (i=0;i<d1+1;i++)
      {
      a=2*i+1;
      if ((a%p!=0)&&((a-1)%p!=0))
        {
         for (j=0;j<(p-1)/2;j++)
          {
           jj=2*j;
           djj=(2*p-k-jj)%(p-1);
           tmp0=(((p+modpow(4,jj,p)-modpow(2,jj,p))%p)*inv[2])%p;
           tmp0d=(((p+modpow(4,djj,p)-modpow(2,djj,p))%p)*inv[2])%p;
           tmp4=(((p+modpow((4*a)%p,jj,p)
                        -modpow((2*a)%p,jj,p))%p)*inv[2])%p;	       
           tmp4d=(((p+modpow((4*a)%p,djj,p)
                        -modpow((2*a)%p,djj,p))%p)*inv[2])%p;
           tmp1=(p+modpow(4,jj,p)-modpow(2,jj,p))%p; 
           tmp1d=(p+modpow(4,djj,p)-modpow(2,djj,p))%p;
           if (a%4==1)
             {
              tmp2=modpow((a-1)%p,jj,p);
              tmp2d=modpow((a-1)%p,djj,p);
             }
           else
             {
              tmp2=(p+modpow((2*(a-1))%p,jj,p)-modpow((a-1)%p,jj,p))%p;
              tmp2d=(p+modpow((2*(a-1))%p,djj,p)-modpow((a-1)%p,djj,p))%p;
             }
           tmp3=(p+modpow((4*a)%p,jj,p)-modpow((2*a)%p,jj,p))%p;
           tmp3d=(p+modpow((4*a)%p,djj,p)-modpow((2*a)%p,djj,p))%p;
           tmp=(2*p+tmp0-tmp1+tmp3-tmp4)%p;
           tmp=(tmp*((p+tmp0d-tmp1d+tmp2d)%p))%p;
           tmppp=(e[i][d2+1]+(tmp*rel1[j])%p)%p;
           e[i][d2+1]=tmppp;           
          } /* for j */
        } /* if a */
      }/* for i*/


   minval=1;
   i=0;
   while((minval!=0)&&(i<d2+1))
     {
     minval=0;
     i2=i;
     while((minval==0)&&(i2<d2+1)) 
       {     
        i1=i;
        while((minval==0)&&(i1<d1+1))
          {
          if (e[i1][i2]%p!=0)
            {
             i1m=i1;
             i2m=i2;
             minval=1;
            }
          i1++;
         }
        i2++; 
       }
    
     if (minval!=0)
       {
       if (i!=i1m)
         {
         for (i2=0;i2<d2+2;i2++)
           {
            tmp=e[i][i2];
            e[i][i2]=e[i1m][i2];
            e[i1m][i2]=tmp;
           }
         }
       if (i!=i2m)
         {
         for (i1=0;i1<d1+1;i1++)   
          {     
            tmp=e[i1][i];
            e[i1][i]=e[i1][i2m];
            e[i1][i2m]=tmp;
          }
         }
       tmp=vr[i];
       vr[i]=vr[i2m];
       vr[i2m]=tmp;

       tmp=e[i][i];
       tmp=inv[tmp];
       for (i1=i+1;i1<d1+1;i1++)
         {
          tmpp=(e[i1][i]*tmp)%p;
          for (i2=i;i2<d2+2;i2++)
            {
             tmppp=(p+e[i1][i2]-((tmpp*e[i][i2])%p))%p;
             e[i1][i2]=tmppp; 
            }
         }
        }/*if*/
        i++;
     }/*while*/


   for (j=0;j<d2+1;j++)
     {
        vrw[vr[j]]=j;   
     }

   im=0;
   while((e[im][im]!=0)&&(im!=d2+1))
     {
       im++;
     }
  
   fprintf(file4,"%lld %lld %lld %lld \n",p,k,im,d2+1);

    
   if (im!=d2+1)
     {
     printf("+++\n");
     fprintf(file4,"+++\n");
     }
    

   tmp=0;
   j=im;
   while(tmp!=1) 
    {
     j--;
     rel[j]=(p-e[j][d2+1])%p;
     for (i2=j+1;i2<d2+1;i2++)
       {
        rel[j]=(p+rel[j]-(e[j][i2]*rel[i2])%p)%p;
       }
     rel[j]=(inv[e[j][j]]*rel[j])%p;
     if (j==0)
       {
        tmp=1;
       }
     }

   for (j=0;j<(p-1)/2;j++)
     {
     if (sg[j]==1)
       {
        rel4[j]=rel[vrw[wrw[j]]];
       }
     else
       {
        rel4[j]=(p-rel[vrw[wrw[dl[j]]]])%p;
       }
       fprintf(file4,"%lld ",rel4[j]);
     } 
     fprintf(file4,"\n");
  }

}/* while */

  fclose(file0);
  fclose(file1);
  fclose(file4);


 }/*main*/ 



unsigned long long int modpow(unsigned long long int a, unsigned long long int b, unsigned long long int m)
{
  unsigned long long int x=1,y,bb;
 
  bb=b;
  y=a;
  while(bb>0)
    {
     if (bb%2==1)
       { 
        x=(x*y)%m;
       }
     y=(y*y)%m;
     bb=bb/2;
    }
  return(x);
}