美好的憧憬

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

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

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

如果从来年的第一天算起,之后再以每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。

情人节邀请赛之木姐姐的情人节梦录[Marathon]

未参加
状态
已结束
规则
OI
题目
20
开始于
2015-02-13 12:00
结束于
2015-02-15 12:00
持续时间
48.0 小时
主持人
参赛人数
273