很多人都知道Morello是LXL世界最强的魔法师，但却不知道他其实还是这个世界上最成功的数学家——他成功地用他的魔法隐藏了他的身份！ 今天，年轻的Karthus想要拜Morello为师。他花了九牛二虎之力终于找到了Morello的住所，Morello却刁钻地给Karthus出了一个数学题，只有他做出来才能成功拜师。 Morello的数学题是这样的： 给定一个算式，要求计算这个式子的结果的约数个数。 （假如a，b均为正整数，且a整除b，则我们认为a是b的约数） 然而，Morello很快就发现了问题，他发现Karthus是个魔法天才，但是数学能力却很一般。Morello现在非常想收Karthus为徒，于是他降低了问题的难度，并且请身为ACMer的你来帮他。 简化问题后，Morello的算式只可能为两种： (a^b)*c； (a*b)^c。 注意：这里的^表示的是幂运算，算式满足1 <= a，b，c <= 1000000，而且你只需计算最终结果 mod 1000000007。

输入数据的第一行是一个整数T（1 < T <= 10000），表示有T组测试数据。 每组数据只有一行，即四个整数 k a b c，其中，k = 1 表示是第一种算式，k = 2 表示是第二种算式，a，b，c的含义见题目描述。

对于每组数据输出一行，输出格式是“Case #c: ans”，参见样例输出。

第一组数据：k = 1， 式子为(3^4)*5 = 405。405有如下10个约数：1 3 5 9 15 27 45 81 105 405。