/* cup14x-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=3*maxp/4,q2=maxp/2,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;
  unsigned long long int inv[maxp];
  unsigned long long int rel[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;

  file0=fopen("bcn4.txt","r");
  file1=fopen("relation4.txt","w");
  
while(fscanf(file0,"%lld %lld %lld %lld %lld\n",&p,&k,&d,&u,&ty)!=EOF)
  {
   if ((p>maxp-1000)&&(p<maxp))
     {
      d1=(3*p)/4;
      d2=(p-3)/2;
  
      for (j=0;j<d2+1;j++)
        {
         vr[j]=j;
        }

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

      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=i;
         if ((a%p!=0)&&((a-1)%p!=0))
           {
            for (j=0;j<d2+1;j++)
              {
               jj=2*j+1;
               djj=(2*p-k-jj)%(p-1);
               if (a%2==1)
                 {
                  if (a%4==1)
                    {
                     sa=1;
                    }
                  else
                    {
                     sa=p-1;
                    }
                  tmp0=(((p+modpow(4,djj,p)-modpow(2,djj,p))%p)*inv[2])%p;
                  tmp4=(((p+modpow((4*a)%p,djj,p)
                        -modpow((2*a)%p,djj,p))%p)*inv[2])%p;
                  tmp1=(p+modpow(4,djj,p)-modpow(2,djj,p))%p;
                  if (a%4==1)
                    {
                     tmp2=modpow((a-1)%p,djj,p);
                    }
                  else
                    {
                     tmp2=(p+modpow((2*(a-1))%p,djj,p)-modpow((a-1)%p,djj,p))%p;
                    }
                  tmp3=(p+modpow((4*a)%p,djj,p)-modpow((2*a)%p,djj,p))%p;

                  tmp=(p+1-(sa*modpow(a%p,jj,p))%p)%p;
                  tmp=(tmp*(p+tmp0-tmp1+tmp2)%p)%p;
                  e[i][j]=tmp;

                  tmp=(2*p+tmp0-tmp1+tmp3-tmp4)%p;
                  e[i][j]=(p+e[i][j]-tmp)%p;
                 }
               else
                 {
                  if (a%4==2)
                    {
                     sa=1;
                    }
                  else
                    {
                     sa=p-1;
                    }
                  tmp0=(((p+modpow(4,djj,p)-modpow(2,djj,p))%p)*inv[2])%p;
                  tmp4=(modpow(2*a,djj,p)*inv[2])%p;
                  tmp1=(p+modpow(4,djj,p)-modpow(2,djj,p))%p;
                  if (a%4==0)
                    {
                     tmp2=modpow(a%p,djj,p);
                    }
                  else
                    {
                     tmp2=(p+modpow((2*a)%p,djj,p)-modpow(a%p,djj,p))%p;
                    }
                  tmp3=(p+modpow((4*(a-1))%p,djj,p)-modpow((2*(a-1))%p,djj,p))%p;

                  tmp=(2*p+tmp0-tmp1+tmp3-tmp4)%p;
                  e[i][j]=tmp;

                  tmp=(p+1-(sa*modpow(a-1,jj,p))%p)%p;
                  tmp=(tmp*(p+tmp0-tmp1+tmp2)%p)%p;
                  e[i][j]=(p+e[i][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*/


    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<d2+1;j++)
        {
         fprintf(file1,"%lld ",rel[vrw[j]]);
        } 
      fprintf(file1,"\n");

     }/* if p */

  }/* while */


  fclose(file0);
  fclose(file1);


 }/*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);
}