#include <bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 const int M = 1e2+;

 const LL mod = 1e9+;

 int ncase,n,m,cas=;

 int vis[M][M];

 LL fac[M];

 void init()

 { ///预处理阶乘

     fac[]=;fac[]=;

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

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

 }

 LL quick_pow(LL p,LL k) ///快速幂

 {

     LL res=,tp=p;

     if(k<) return ;

     while(k){

         if(k&) res=res*tp%mod;

         tp=tp*tp%mod;

         k>>=;

     }

     return res;

 }

 LL C(int n,int m)

 {

     return fac[n]*quick_pow(fac[m],mod-)%mod*quick_pow(fac[n-m],mod-)%mod;

 }///费马小定理求逆元+快速幂

 int judge(int i,int j,int k){ ///判断三点之间满不满足不稳定点集

     if(vis[i][j]&&vis[i][k]&&vis[j][k]) return ;///三点之间相连

     if(!vis[i][j]&&!vis[i][k]&&!vis[j][k]) return ; ///三点之间不互联

     return ;

 }

 int judge1(int i,int j,int k,int l)

 {

     if(judge(i,j,k)||judge(i,j,l)||judge(j,k,l)||judge(i,k,l)) return ; ///表示4个点中有三个点为不稳定点集就行,为什么呢？

     ///因为时题目要求的，不稳定点集为3个点。

     return ;

 }

 int judge2(int i,int j,int k,int l,int o){

     ///表示5个点中有4个点满足就行

     if(judge1(i,j,k,l)||judge1(i,j,k,o)||judge1(i,j,l,o)||judge1(j,k,l,o)||judge1(i,k,l,o)) return ;

     return ;

 }

 int main(){

     init();

     scanf("%d",&ncase);

     while(ncase--){

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

         memset(vis,false,sizeof(vis));

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

             int u,v;

             scanf("%d%d",&u,&v);

             vis[u][v]=vis[v][u]=;

         }

         LL ans=;

         if(n>=){

             ans=(ans+quick_pow(,n))%mod; ///多项式定理C(n,0)+C(n,1)+...+C(n,n)=2^n

             ///C(n,k)(k>=6)表示，从n个中取k个出来，总存在一个不稳定点集的个数（三点之间互联或三点之间不连）

             for(int i=;i<;i++) ///减去前5个

                 ans=(ans-C(n,i)+mod)%mod;

         }

         if(n>=){  ///暴力取3个

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

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

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

                         if(judge(i,j,k)) ans=(ans+)%mod;

         }

         if(n>=){ ///暴力取4个

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

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

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

                         for(int l=k+;l<=n;l++)

                             if(judge1(i,j,k,l)) ans=(ans+)%mod;

         }

         if(n>=){ ///暴力取5个

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

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

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

                         for(int l=k+;l<=n;l++)

                             for(int o=l+;o<=n;o++)

                                 if(judge2(i,j,k,l,o)) ans=(ans+)%mod;

         }

         printf("Case #%d: %lld\n",cas++,ans);

     }

     return ;}