描述

木姑娘在上海的那几天，是我最幸福的时光。

木姑娘喜欢吃很多好吃的，于是我便和她计划着，以后要每天带她吃好吃的。

如果从来年的第一天算起，之后再以每n天作为一个周期去安排木姑娘每日的点心。这个想法真是好极了。

而我可以想到的点心，一共有m种类。

只要给木姑娘安排的每日点心满足相邻两天不相同，应该就可以天天看到木姑娘的笑容吧。

格式

输入格式

第一行有一个整数T，表示有T组数据。

对于每一组数据，给出2个整数n和m。1<=n,m<=1000000000。

输出格式

输出有T行，对应T组数据。

对于每一组数据，先给出数据编号，之后输出可能的点心安排策略总数，你只需要给出mod 1000000007后的余数。

详请参加样例输出。

样例1

样例输入1

3
4 3
4 4
5 2

样例输出1

Case #1: 18
Case #2: 84
Case #3: 0

限制

对于30％的数据，n,m<=5。
对于100％的数据，n,m<=1000000000。