#include<bits/stdc++.h>

 using namespace std;

 # define ll long long

 # define inf 0x3f3f3f3f

 const int maxn = 2e5+;

 const int mod = 1e9+;

 ll c[+][+];

 char str[maxn];

 ll s1[+][maxn],s2[+][maxn];

 ll ind(int t1,int t2)

 {

     if(t2&)

         return -1ll;

     return 1ll;

 }

 void init()

 {

     c[][]=1ll;

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

     {

         c[i][]=1ll;

         for(int j=; j<=i; j++)

         {

             c[i][j]=(c[i-][j]+c[i-][j-])%mod;

         }

     }

 }

 int  main()

 {

     init();

     int T;

     scanf("%d",&T);

     while(T--)

     {

         int n,k;

         scanf("%d %d",&n,&k);

         scanf("%s",str);

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

         {

             s1[][i]=1ll;

         }

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

         {

             s1[][i]=(s1[][i-]+(ll)(str[i-]-''));

         }

         for(int i=; i<=k; i++)

         {

             for(int j=; j<=n; j++)

             {

                 s1[i][j]=s1[i-][j]*s1[][j]%mod;

             }

         }

         s2[][]=1ll;

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

         {

             for(int j=; j<=k; j++)

             {

                 s2[j][i]=(s2[j][i-]+s1[j][i])%mod;

             }

         }

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

         {

             ll ans=;

             for(int j=; j<=k; j++)

             {

                 ll tmp=c[k][j]*s1[j][i]%mod*s2[k-j][i-]%mod;

                 if(ind(-,k-j)==1ll)

                     ans=(ans+tmp)%mod;

                 else

                     ans=(ans-tmp+mod)%mod;

             }

             if(i!=)

                 printf(" ");

             printf("%lld",ans);

         }

         printf("\n");

     }

     return ;

 }