John's Tree

ll xtr(){
    if(!d)return 1;
    if(d==1)return (v+1)%M;
    if(v==1)return -1;
    if(v==2)return ((v*d)+1)%M;
    //Here implement the formula ( http://www.wolframalpha.com/input/?i=%28%28%28v-1%29%5Ed-1%29v%29%2F%28v-2%29%2B1 )
}
int main(void){
    IN(tt)F(tt){
        scanf("%lld%lld",&d,&v);
        printf("Case %d: %lld\n",i+1,xtr());
    }
    return 0;
}