#include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 ll moder=1e9+;

 int T;

 ll a[],c[];

 ll ksm(ll a,ll b)

 {

     ll ans=;

     while(b)

     {

         if(b&) ans=ans*a%moder;

         b>>=;

         a=a*a%moder;

     }

     return ans%moder;

 }

 int main()

 {

     scanf("%d",&T);

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

     {

         ll n=;int k=;

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

         for(int j=;j<=k;j++) a[j]=,c[j]=;

         a[]=;c[]=;

         ll sum=;//c[0]

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

         {

             a[j]=-(moder/j)*a[moder%j];

             a[j]=(a[j]%moder+moder)%moder;

         }

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

         {

             c[j]=(c[j-]%moder*(n-j+)%moder*a[j]%moder)%moder;

             sum=(sum+c[j])%moder;

         }

         ll t=ksm(,n);

         printf("Case #%d: %lld\n",i,((t+moder)-sum)%moder);

     }

     return ;

 }